Python实现最短路径算法（小白也能看懂的Dijkstra算法详解）

准备工作：理解图的表示方式

在 Python 中，我们通常使用字典来表示图。每个节点作为键，其值是一个包含邻居节点及对应边权重的字典。例如：

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

上面的图表示：从 A 到 B 的距离是 1，从 A 到 C 是 4，依此类推。

Python实现Dijkstra算法

下面我们将一步步实现 Dijkstra 算法。我们将使用 heapq 模块（最小堆）来高效地获取当前距离最小的节点。

import heapqdef dijkstra(graph, start):    # 初始化：所有节点的距离设为无穷大，起点设为0    distances = {node: float('infinity') for node in graph}    distances[start] = 0    # 优先队列：存储 (距离, 节点)    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] = distance                heapq.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}}# 从节点 'A' 开始计算最短路径result = dijkstra(graph, 'A')print(result)# 输出: {'A': 0, 'B': 1, 'C': 3, 'D': 4}

代码解析

• 初始化距离字典：将所有节点的距离设为无穷大（float('infinity')），只有起点为 0。
• 优先队列：使用最小堆（heapq）来始终处理当前距离最小的节点，这是 Dijkstra 算法效率的关键。
• 松弛操作：对每个邻居，尝试通过当前节点找到更短的路径。如果成功，就更新距离并将新状态加入队列。

应用场景与扩展

Dijkstra 算法广泛应用于 GPS 导航、网络数据包路由、游戏 AI 路径规划等场景。需要注意的是，该算法不能处理负权边。如果图中存在负权边，应考虑使用 Bellman-Ford 算法。

通过本教程，你已经掌握了如何用 Python 实现最基础但功能强大的 图论算法——Dijkstra 算法。这也是学习更复杂 Python路径查找 技术的重要一步。

总结

本文详细讲解了 Python最短路径算法 的实现过程，重点介绍了 Dijkstra 算法的原理、代码实现和实际应用。无论你是初学者还是有一定经验的开发者，都能通过这段简洁而高效的代码理解图中最短路径的求解逻辑。

动手试试吧！修改图的结构，更换起点，观察输出结果的变化，加深对 Dijkstra算法 的理解。