dijkstra(迪杰斯特拉)算法详解

概念：是一种用于在带权图中计算单源最短路径的经典算法，由荷兰计算机科学家艾兹赫尔·戴克斯特拉于1956年提出。该算法采用贪心策略，逐步确定从源点到其他所有顶点的最短路径，适用于边权非负的有向图或无向图。‌‌

1.1  规则

从起始点开始，采用贪心算法的策略，每次遍历到离起始点距离最近且未访问过的顶点的邻接节点，直到扩展到终点为止。

1.2 实例

 问题：计算从1出发到5最短路径

由图可知，1->2的权值为7,1->3的权值为9,1->6的权值为14,2->4的权值为15，2->3的权值为10,  3->4的权值为11,3->6的权值为2,4->5的权值为6 ，6->5的权值为9

（1）初始化，假设各个节点到1都有连线，无法直连的则标注为∞。所以2的前缀为1，权值为7；3的前缀为1，权值为9；6的前缀为1，权值为14,4 的前缀为1，权值为∞；5的前缀为1，权值为∞

（2）经过比较权值，可以确定1->2（1,2）的最短路径权值为7，选择2作为下一个节点，前缀为1，权值为7,。从2出发，可以到达3和4，但经过比较，到达3的权值为17<9,所以确定1->3(1,3)的最短路径权值为9，前缀为1；此时1->4（1,2,4）的前缀改为2，权值为22

（3）上一步确定1->3的最短路径，此时从3出发，可以到达4和6.则1->6的权值为11<14,此时确定1->6（1,3,6）的最短路径，前缀为3，权值和为11.1->4（1,3,4）的权值为20<22，确定1->4（1,3,4）的最短路径，前缀为3。

（4）上一步确定1->4的最短路径和1->6的最短路径。此时从4出发，可到达并未确定的点为5，权值为26.从6出发到达5的权值为20.可知到达5的最短路径为1->5(1,3,6,5)，前缀为6.

（5）最后，可得知从1到达各个点的最短路径为

到达点	2	3	4	5	6
权值	7	9	20	20	11
最短路径	(1,2)	(1,3)	(1,3,4）	(1,3,6,5)	（1,3,6）

1.3 代码实现：

 

import heapqdef dijkstra(graph, start):# 初始化距离字典：所有节点距离设为无穷大，起点设为0distances = {node: float('inf') for node in graph}distances[start] = 0# 记录每个节点的前驱节点（用于重建路径）predecessors = {node: None for node in graph}# 使用优先队列（最小堆），存储(距离, 节点)priority_queue = [(0, start)]while priority_queue:# 弹出当前距离最小的节点current_distance, current_node = heapq.heappop(priority_queue)# 如果当前距离大于记录的距离，跳过（已找到更优解）if current_distance > distances[current_node]:continue# 遍历邻居节点for neighbor, weight in graph[current_node].items():distance = current_distance + weight# 如果找到更短路径，更新距离和前驱节点if distance < distances[neighbor]:distances[neighbor] = distancepredecessors[neighbor] = current_node  # 记录路径heapq.heappush(priority_queue, (distance, neighbor))return distances, predecessorsdef get_shortest_path(predecessors, start, end):"""根据前驱节点字典重建从起点到终点的路径"""path = []current = end# 从终点回溯到起点while current is not None:path.append(current)current = predecessors[current]# 反转路径（起点->终点）path.reverse()# 检查是否找到有效路径if path[0] != start:return None  # 起点与终点不连通return path# 测试用例
if __name__ == "__main__":# 使用邻接表表示图（字典的字典）graph = {'A': {'B': 1, 'C': 4},'B': {'A': 1, 'C': 2, 'D': 5},'C': {'A': 4, 'B': 2, 'D': 1},'D': {'B': 5, 'C': 1}}start_node = 'A'distances, predecessors = dijkstra(graph, start_node)print("\n从节点 {start_node} 到各节点的最短路径:")for node in graph:if node == start_node:continuepath = get_shortest_path(predecessors, start_node, node)if path:path_str = " → ".join(path)print(f"{start_node} → {node}: {path_str} (距离: {distances[node]})")else:print(f"{start_node} → {node}: 路径不存在")

代码运行效果图：