Dijkstra算法可以计算加权图一个顶点到其它各个顶点的最短路径，权值不能为负数。
算法描述
将一个图的所有顶点分为 S, U 两个集合. S 表示已经求出最短路径的顶点集合， U 表示剩余未确定最短路径的顶点集合。
初始时 S 中只有一个源点，从 U 中选择一个距离源点距离最近的顶点 v 移动到 S 中，以 v 为中间顶点更新源点到 U 中各个顶点的路径长度, 只计算与 v 邻接的顶点就行了,未邻接的顶点说明暂时还不能确定最短路径, 如果找到了更短的路径就更新。重复上面操作直到 U 为空算法结束， S 就保留了源点到各个顶点的最短路径。
步骤分析
初始：
S(A:0)
U(B:6, C:3, D:∞, E:∞, F:∞)
A 为源点，源点到 B 的距离为6，到 C 的距离为 3，到D、E、F的最短路径还未确定所以赋值为无穷大
第一步：
从 U 中选择距离源点路径最短的顶点，显然是 C(3)，把 C 移动到 S 中。
S(A:0, C:3)
U(B:6, D:∞, E:∞, F:∞)
以 C 为中间点，更新源点到 U 中各个顶点的距离(只计算与 C 邻接的顶点就行)
A->C->B=5 < 6, A->C->D=6 < ∞, A->C->E=7 < ∞
更新后:
U(B:5, D:6, E:7, F:∞)
第二步：
再从 U 中选择距离源点路径最短的顶点 B(5)，重复第一步的操作，这里没有需要更新的，计算后得到
S(A:0, C:3, B:5)
U(D:6, E:7, F:∞)
第三步:
从 U 中选择 D(6), A->C->D->F=9 < ∞, 操作后得到
S(A:0, C:3, B:5, D:6)
U(E:7, F:9)
第四步:
从 U 中选择 E(7), 操作后得到
S(A:0, C:3, B:5, D:6, E:7)
U(F:9)
最后一步：
把最后一个顶点 F(9) 移动到 S 中， U 变为空
S(A:0, C:3, B:5, D:6, E:7, F:9)
所以从源点 A 到各个顶点的最短路径为:
A->A 0
A->C 3
A->B 5 (A->C->B)
A->D 6 (A->C->D)
A->E 7 (A->C->E)
A->F 9 (A->C->D->F)
代码实现
python 中可以这样表示上面的无向图
g = {
'A': {'B': 6, 'C': 3},
'B': {'A': 6, 'C': 2, 'D': 5},
'C': {'A': 3, 'B': 2, 'D': 3, 'E': 4},
'D': {'B': 5, 'C': 3, 'E': 2, 'F': 3},
'E': {'C': 4, 'D': 2, 'F': 5},
'F': {'D': 3, 'E': 5}
}
与邻接表类似
无穷大可以这样表示
infinity = float("inf") # 无穷大
#!/usr/bin/env python3
def find_lowest_cost_node(U):
lowest = infinity
lowest_node = None
for k, v in U.items():
if v < lowest:
lowest = v
lowest_node = (k, v)
return lowest_node
def dijkstra():
S = {
'A': 0
}
U = {
'B': 6,
'C': 3,
'D': infinity,
'E': infinity,
'F': infinity
}
while len(U) > 0: # 只要 U 不空就一直循环
# 从 U 中寻找距离源点路径最短的顶点 v
lowest_node = find_lowest_cost_node(U)
# 把顶点 v 从 U 中移动到 S 中
lowest_key, lowest_cost = lowest_node
S[lowest_key] = lowest_cost
del U[lowest_key]
# 寻找与找到的路径最短的顶点的所有邻接顶点
neighbors = g[lowest_key]
for node in neighbors:
if node in U.keys():
pre_cost = U[node]
# 以新找到的顶点重新计算路径长度
new_cost = lowest_cost + neighbors[node]
if new_cost < pre_cost:
U[node] = new_cost # 如果找到了更短的路径则更新 U 中的路径长度
# 因为哈希表输出顺序不固定这里排一下序
print(sorted(S.items(), key=lambda x: x[1]))
# [('A', 0), ('C', 3), ('B', 5), ('D', 6), ('E', 7), ('F', 9)]
最短路径的长度是计算出来了，但经过的顶点没有保存下来，可以再用一个表保存各个顶点的父结点
A B 表示 A的父结点是 B
开始 A没有父结点，B 和 C 的父结点为 A
A None
B A
C A
当 C 移动到 S 中后， A->C>B=5 < A->B=6 所以 B 的父结点应该改为 C， A->C->D=6 < ∞ 所以 D 的父结点为 C， A->C->E=7 < ∞ 所以 E 的父结点为 C
A None
B C
C A
D C
E C
当 D 移动到 S 中后，A->C->D->F=9 < ∞, F的父节点为 D
A None
B C
C A
D C
E C
F D
可见当发现了更短的路径时添加或更新父结点就行了
parent = {
'A': None,
'B': 'A',
'C': 'A'
}
if new_cost < pre_cost:
U[node] = new_cost # 如果找到了更短的路径则更新 U 中的路径长度
parent[node] = lowest_key # 更新父结点
print(sorted(parent.items()))
# [('A', None), ('B', 'C'), ('C', 'A'), ('D', 'C'), ('E', 'C'), ('F', 'D')]
打印路径就非常简单了，这里就不写了
