本文的算法思想来自于知乎的一篇文章。大家可以点击链接去看看，会有意外收获哦。😎
Dijkstra 算法
Dijkstra是一个经典的贪心算法
时间复杂度是 O ( E l o g E ) O(ElogE) O(ElogE)，其中 E E E 是节点数的最大值。
基本思想
通过Dijkstra计算图G中的最短路径时，需要指定一个起点D(即从顶点D开始计算)。
此外，引进两个数组S和U。S的作用是记录已求出最短路径的顶点(以及相应的最短路径长度)，而U则是记录还未求出最短路径的顶点(以及该顶点到起点D的距离)。
初始时，数组S中只有起点D；数组U中是除起点D之外的顶点，并且数组U中记录各顶点到起点D的距离。如果顶点与起点D不相邻，距离为无穷大。
然后，从数组U中找出路径最短的顶点K，并将其加入到数组S中；同时，从数组U中移除顶点K。接着，更新数组U中的各顶点到起点D的距离（即更新与K相连的边到起点的距离，在通过K与不通过K二者之间寻找较小值）。
重复第4步操作，直到遍历完所有顶点。
上面这幅图来自于B站的一个视频。大家可以点击链接去看看，会有意外收获哦。😎
构造图
def create_graph():edges = []for i in range(9):edges.append([])for j in range(9):edges[i].append(0 if j==i else float('inf'))edges[0][1] = 4edges[0][7] = 8edges[1][0] = 4edges[1][2] = 8edges[1][7] = 3edges[2][1] = 8edges[2][3] = 7edges[2][5] = 4edges[2][8] = 2edges[3][2] = 7edges[3][4] = 9edges[3][5] = 14edges[4][3] = 9edges[4][5] = 10edges[5][2] = 4edges[5][3] = 14edges[5][4] = 10edges[5][6] = 2edges[6][5] = 2edges[6][7] = 6edges[6][8] = 6edges[7][0] = 8edges[7][1] = 3edges[7][6] = 6edges[7][8] = 1edges[8][2] = 2edges[8][6] = 6edges[8][7] = 1return edges
本例计算 0 → 4 的最短距离
graph = create_graph()graph
[[0, 4, inf, inf, inf, inf, inf, 8, inf],[4, 0, 8, inf, inf, inf, inf, 3, inf],[inf, 8, 0, 7, inf, 4, inf, inf, 2],[inf, inf, 7, 0, 9, 14, inf, inf, inf],[inf, inf, inf, 9, 0, 10, inf, inf, inf],[inf, inf, 4, 14, 10, 0, 2, inf, inf],[inf, inf, inf, inf, inf, 2, 0, 6, 6],[8, 3, inf, inf, inf, inf, 6, 0, 1],[inf, inf, 2, inf, inf, inf, 6, 1, 0]]
# 计算字典中values中最小值所在的所有键值对def get_min_value_pairs(dic):min_value = min(dic.values())# 下面这条语句可以找到代表min_value的多个keykeys = [k for k, v in dic.items() if v == min_value]# 返回所有的最小值的键值对return [(k, dic[k]) for k in keys]
def Dijkstra(start, end, graph):nodes_num = len(graph)S = {} # 已计算出起点到定点最短路径的定点集合U = {} # 未计算出起点到定点最短路径的定点集合# 键值对 4:8 表示起点到定点4的最短距离为8# 初始化 S 和 US[start] = 0 # 起点到自己的最短距离为 0 for i in range(nodes_num):U[i] = graph[start][i]# 开始计算while len(U) > 0:# 在 U 中寻找到起点距离最短的节点，将其插入 S 中，并在 U 中移除min_dis_node, min_dis = get_min_value_pairs(U)[0]S[min_dis_node] = min_disU.pop(min_dis_node)# 更新 U 中与新插入到 S 中的点对其相邻点到起点的距离值for key in list(U.keys()):if graph[min_dis_node][key] != float('inf'): # 找到与新插入点相连的顶点U[key] = min(U[key], min_dis + graph[min_dis_node][key])return S
pairs = Dijkstra(0, 4, graph)print(pairs)print('0→4 的最短距离为 {0}'.format(pairs[4]))
{0: 0, 1: 4, 7: 7, 8: 8, 2: 10, 6: 13, 5: 14, 3: 17, 4: 24}0→4 的最短距离为 24
