Day.19 Dijkstra

Dijkstra

如果我们想知道A点到E点之间的最短路径，我们要怎麽做？
在边值不是负的情况下，都可以使用Dijkstra算法，像两点之间的距离不存在负值，就很适合用Dijkstra，如果有负值的图，需要用Bellman-Ford的算法。

Dijkstra算法是BFS的延伸，搜寻方式一样是以广度优先。
现在来大概说明一下算法的流程～

我们需要先定义一个map来记各点的最短距离

type ShortestPath struct {
	Distance  int
	PreVertex *Vertex
}

map[*Vertex]*ShortestPath

从A点出发，先到B点，记录到B的最短距离为1。A再去C点，到C最短距离为6。
现在map的记录为:

B: {Distance:1, PreVertex:A}
C: {Distance:6, PreVertex:A}

A已经走完了，现在换B、C往外搜寻
B到C的距离为2，A到B的距离+2=3，目前map里面C的最短路离为6，3<6，更新C最短距离为3
B到D距离1，A到B的距离+1=2，更新D最短距离为2
C到E，距离为3+5=8，更新E最短距离
C到B，距离为6+2=8，大於原本的1，不更新

map:

B: {Distance:1, PreVertex:A}
C: {Distance:3, PreVertex:B}
D: {Distance:2, PreVertex:B}
E: {Distance:8, PreVertex:C}

重复这个过程，把全部的点跟边都走完，就可以得知从A出发全部点的最短距离～
如果我们要知道整个路径的走法，就从PreVertex回溯就可以了
ex. E->C->B->A

程序：

type ShortestPath struct {
	Distance  int
	PreVertex *Vertex
}

func (g *Graph) Dijkstra(target *Vertex) map[*Vertex]*ShortestPath {
	path := map[*Vertex]*ShortestPath{}
	visted := g.getVistedVertex() // 用来记录走过的顶点
	visted[target] = true
	queue := []*Vertex{
		target,
	}

	// 初始化距离
	for v := range visted {
		path[v] = &ShortestPath{
			Distance: 0,
		}
	}

	index := 0
	for index < len(queue) {
		for _, edge := range g.adjList[queue[index]] {
			if !visted[edge.Vertex] {
				queue = append(queue, edge.Vertex)
				visted[edge.Vertex] = true
			}

			// 目前vertex的最短距离 + edge的距离
			totalDistance := path[queue[index]].Distance + edge.Distance

			// 第一次到这个点 or 距离比较近 就去更新最短路径
			if path[edge.Vertex].Distance == 0 || path[edge.Vertex].Distance > totalDistance {
				path[edge.Vertex] = &ShortestPath{
					Distance:  totalDistance,
					PreVertex: queue[index],
				}
			}
		}

		index++
	}

	return path
}

// 显示出整个路径
func (g *Graph) ShowShortestPath(start *Vertex, end *Vertex) {
	allPath := g.Dijkstra(start)
	vertexPath := []*Vertex{}

	path := allPath[end]
	distance := path.Distance
	for path.PreVertex != nil {
		vertexPath = append(vertexPath, path.PreVertex)
		path = allPath[path.PreVertex]
	}

	str := ""
	for i := len(vertexPath) - 1; i >= 0; i-- {
		str += vertexPath[i].Name + "->"
	}
	str += end.Name

	fmt.Printf("distance: %v, path: %v \n", distance, str)
}

func main() {
	a := &Vertex{
		Name: "A",
	}
	b := &Vertex{
		Name: "B",
	}
	c := &Vertex{
		Name: "C",
	}
	d := &Vertex{
		Name: "D",
	}
	e := &Vertex{
		Name: "E",
	}

	g := newGraph()
	g.AddVertex(a)
	g.AddVertex(b)
	g.AddVertex(c)
	g.AddVertex(d)
	g.AddVertex(e)

	// A的边
	g.AddEage(a, b, 1)
	g.AddEage(a, c, 6)
	// B的边
	g.AddEage(b, c, 2)
	g.AddEage(b, d, 1)
	// C的边
	g.AddEage(c, b, 2)
	g.AddEage(c, d, 2)
	g.AddEage(c, e, 5)
	// D的边
	g.AddEage(d, e, 10)

    g.ShowShortestPath(a, e)
}

output:

distance: 8, path: A->B->C->E 

明天来解leetcode~