使用 Python 实现 Dijkstra 算法

1. Dijkstra 算法的基本概念

2. 工作原理

3. Python 实现

图的表示

Dijkstra 算法实现

4. 代码详解

初始化

主循环

返回结果

5. 总结

使用 Python 实现 Dijkstra 算法

Dijkstra 算法是一种用于解决图中单源最短路径问题的经典算法。它由荷兰计算机科学家 Edsger W. Dijkstra 于 1956 年提出。本文将详细介绍 Dijkstra 算法的基本概念、工作原理，并提供一个使用 Python 实现的示例。

1. Dijkstra 算法的基本概念

Dijkstra 算法用于在一个带权重的图中找到从一个起点到其他所有顶点的最短路径。算法的主要思想是从起点开始，逐步扩展已知最短路径的顶点集合，直到所有顶点都被包含在内。

2. 工作原理

初始化：将起点的距离设为 0，其他所有顶点的距离设为无穷大（表示未知）。
选择最小距离顶点：从未被处理的顶点中选择距离最小的顶点。
更新邻接顶点的距离：对于选定的顶点，更新其所有邻接顶点的距离。
标记顶点为已处理：将选定的顶点标记为已处理。
重复步骤 2-4：直到所有顶点都被处理完毕。

3. Python 实现

下面是一个使用 Python 实现 Dijkstra 算法的示例。我们将使用一个简单的图来演示算法的工作过程。

图的表示

我们将使用邻接表来表示图。邻接表是一个字典，其中键是顶点，值是一个包含相邻顶点及其权重的列表。

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}
}

Dijkstra 算法实现

import heapqdef dijkstra(graph, start):# 初始化距离字典，所有顶点的距离初始为无穷大distances = {vertex: float('infinity') for vertex in graph}distances[start] = 0# 初始化优先队列，存储 (距离, 顶点) 对priority_queue = [(0, start)]while priority_queue:# 弹出距离最小的顶点current_distance, current_vertex = heapq.heappop(priority_queue)# 如果当前距离大于已知最短距离，跳过if current_distance > distances[current_vertex]:continue# 更新邻接顶点的距离for neighbor, weight in graph[current_vertex].items():distance = current_distance + weight# 如果找到更短的路径，更新距离并加入优先队列if distance < distances[neighbor]:distances[neighbor] = distanceheapq.heappush(priority_queue, (distance, neighbor))return distances# 示例图
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_vertex = 'A'# 计算最短路径
shortest_distances = dijkstra(graph, start_vertex)
print(shortest_distances)  # 输出 {'A': 0, 'B': 1, 'C': 3, 'D': 4}

4. 代码详解

初始化

距离字典：distances 字典用于存储每个顶点的最短距离，初始时所有顶点的距离为无穷大，起点的距离为 0。
优先队列：priority_queue 是一个最小堆，用于存储待处理的顶点及其距离。

distances = {vertex: float('infinity') for vertex in graph}
distances[start] = 0
priority_queue = [(0, start)]

主循环

弹出距离最小的顶点：使用 heapq.heappop 从优先队列中弹出距离最小的顶点。
跳过已处理的顶点：如果当前顶点的距离大于已知最短距离，跳过该顶点。
更新邻接顶点的距离：对于当前顶点的每个邻接顶点，计算新的距离，如果新的距离更短，则更新距离并将其加入优先队列。

while priority_queue:current_distance, current_vertex = heapq.heappop(priority_queue)if current_distance > distances[current_vertex]:continuefor neighbor, weight in graph[current_vertex].items():distance = current_distance + weightif distance < distances[neighbor]:distances[neighbor] = distanceheapq.heappush(priority_queue, (distance, neighbor))