Dijkstra算法详解（Python语言实现最短路径查找）

Dijkstra 算法的基本思想

算法的核心思想是“贪心”策略：

1. 初始化：设置起点到自身的距离为0，到其他所有点的距离为无穷大（∞）。
2. 从未确定最短路径的节点中，选择当前距离最小的节点。
3. 用该节点更新其邻居节点的距离（松弛操作）。
4. 重复步骤2-3，直到所有节点都被处理。

Python 实现 Dijkstra 算法

下面我们使用 Python 的 heapq 模块（优先队列）来高效实现 Dijkstra 算法。

import heapqdef dijkstra(graph, start):    """    使用 Dijkstra 算法计算从 start 节点到图中所有其他节点的最短路径        :param graph: 字典表示的图，例如 { 'A': {'B': 1, 'C': 4}, ... }    :param start: 起始节点（字符串或数字）    :return: 字典，包含从 start 到每个节点的最短距离    """    # 初始化距离字典：所有节点初始距离为无穷大    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("从 A 出发的最短路径距离：")for node, dist in result.items():    print(f"{node}: {dist}")

代码解析

• graph：用嵌套字典表示图，外层键是节点，内层键是邻居节点，值是边的权重。
• distances：存储从起点到每个节点的最短距离。
• priority_queue：使用最小堆（heapq）确保每次处理距离最小的未访问节点。
• 松弛操作：如果通过当前节点到达邻居的距离更短，就更新邻居的距离。

运行结果

运行上述代码，输出如下：

从 A 出发的最短路径距离：A: 0B: 1C: 3D: 4

应用场景与总结

Dijkstra 算法是图论算法教程中的核心内容之一，适用于 GPS 导航、网络数据包路由、社交网络分析等场景。通过本教程，你已经掌握了如何用 Python 最短路径 实现 Dijkstra 算法。

记住：Dijkstra 算法不能处理负权边。如果图中存在负权边，请考虑使用 Bellman-Ford 算法。

希望这篇 Dijkstra算法实现 教程对你有所帮助！动手试试修改图结构，看看结果如何变化吧！