最短路径算法-Dijkstra

算法描述

这个算法是通过为每个顶点 v 保留目前为止所找到的从 s 到 v 的最短路径来工作的。初始时,原点 s 的路径权重被赋为 0 (d[s] = 0)。若对于顶点 s 存在能直接到达的边(s,m),则把 d[m]设为 w(s, m),同时把所有其他(s 不能直接到达的)顶点的路径长度设为无穷大,即表示我们不知道任何通向这些顶点的路径(对于所有顶点的集合 V 中的任意顶点 v, 若 v 不为 s 和上述 m 之一, d[v] = ∞)。当算法结束时,d[v] 中存储的便是从 s 到 v 的最短路径,或者如果路径不存在的话是无穷大。
边的拓展是 Dijkstra 算法的基础操作:如果存在一条从 u 到 v 的边,那么从 s 到 v 的最短路径可以通过将边(u, v)添加到尾部来拓展一条从 s 到 v 的路径。这条路径的长度是 d[u] + w(u, v)。如果这个值比目前已知的 d[v] 的值要小,我们可以用新值来替代当前 d[v] 中的值。拓展边的操作一直运行到所有的 d[v] 都代表从 s 到 v 的最短路径的长度值。此算法的组织令 d[u] 达到其最终值时,每条边(u, v)都只被拓展一次。
算法维护两个顶点集合 S 和 Q。集合 S 保留所有已知最小 d[v] 值的顶点 v ,而集合 Q 则保留其他所有顶点。集合 S 初始状态为空,而后每一步都有一个顶点从 Q 移动到 S。这个被选择的顶点是 Q 中拥有最小的 d[u] 值的顶点。当一个顶点 u 从 Q 中转移到了 S 中,算法对 u 的每条外接边 (u, v) 进行拓展。

如下图:

代码实现-Golang

github

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
package ShortestPath

import (
"errors"

"container/list"

"github.com/mohuishou/algorithm/Graph"
)

//INF 无穷大
const INF = 0xffffff

//Dijkstra 算法
//一种求单源最短路径的算法
func Dijkstra(graph Graph.Graph, s Graph.VextexType, dist []Graph.EdgeType, path []Graph.VextexType) {
visited := make([]bool, graph.VNum)
//初始化
for i := 0; i < graph.VNum; i++ {
dist[i] = INF //距离为无穷大
path[i] = -1 //没有上一个节点
visited[i] = false
}
path[s] = s
dist[s] = 0

//使用list实现一个队列操作
q := list.New()

//将点s入队
q.PushBack(s)
for q.Len() != 0 {
u := q.Front().Value.(Graph.VextexType)
q.Remove(q.Front())
//如果该点周围的点已经走过,则无需再走
if visited[u] {
continue
}

//将该点加入已观察
visited[u] = true

e := graph.G[u].FisrtEdge

for e != nil {
//这条边下的顶点
v := e.V

//如果该点尚未走过,并且当前点的距离加上边的距离小于之前该点的距离,那么就更新该点的距离
if visited[v] == false && dist[v] > dist[u]+e.Weight {
dist[v] = dist[u] + e.Weight //更新该点距离
path[v] = u //更新父节点
q.PushBack(v) //将该点入队
}
e = e.Next
}

}

}

//GetPath 通过路径获得到指定目的节点的路径
func GetPath(path []Graph.VextexType, t Graph.VextexType) ([]Graph.VextexType, error) {
tPath := make([]Graph.VextexType, 0)
for {
tPath = append(tPath, t)
if path[t] == -1 {
return nil, errors.New("不存在到该节点的路径")
}
if t == path[t] {
return tPath, nil
}
t = path[t]
}
}