概述

Dijkstra 算法是一种用于计算加权图中从单个源节点到其他所有节点的最短路径的经典算法。它通过维护一个集合来存储已找到最短路径的节点，以及一个优先队列来存储尚未找到最短路径的节点，每次从优先队列中选择距离源节点最近的节点，并更新其邻居节点的距离。

本文将详细介绍 Dijkstra 算法的原理，并通过具体的 Python 代码示例来展示其实现过程。

Dijkstra 算法原理

1. 初始化：

   • 初始化一个字典 distances，用于存储从源节点到每个节点的最短距离，初始值为无穷大。
   • 将源节点的初始距离设为 0。
   • 使用一个优先队列 queue 存储待处理的节点及其当前距离，初始时将源节点及其距离 0 放入队列。

2. 主循环：

   • 从优先队列中取出距离最小的节点及其距离。
   • 如果当前节点的距离大于 distances 中记录的距离，则跳过该节点。
   • 遍历当前节点的所有邻居节点，计算从当前节点到邻居节点的距离。
   • 如果计算出的新距离小于 distances 中记录的距离，则更新 distances 并将邻居节点及其新距离加入优先队列。

3. 返回结果：

   • 返回 distances 字典，其中每个键对应一个节点，每个值是从源节点到该节点的最短距离。

Python 实现

import heapq

def dijkstra(graph, start):
    # 初始化距离字典，所有节点的初始距离为无穷大
    distances = {node: float('inf') for node in graph}
    # 源节点的初始距离为 0
    distances[start] = 0
    # 初始化优先队列，存储待处理的节点及其当前距离
    queue = [(0, start)]

    while queue:
        # 从优先队列中取出距离最小的节点及其距离
        current_distance, current_node = heapq.heappop(queue)

        # 如果当前节点的距离大于 distances 中记录的距离，跳过该节点
        if current_distance > distances[current_node]:
            continue

        # 遍历当前节点的所有邻居节点
        for neighbor, weight in graph[current_node].items():
            # 计算从当前节点到邻居节点的距离
            distance = current_distance + weight

            # 如果计算出的新距离小于 distances 中记录的距离
            if distance < distances[neighbor]:
                # 更新 distances
                distances[neighbor] = distance
                # 将邻居节点及其新距离加入优先队列
                heapq.heappush(queue, (distance, neighbor))

    # 返回从源节点到所有节点的最短距离
    return distances

代码详解

1. 导入必要的模块

import heapq

• heapq：Python 内置的堆队列模块，用于实现优先队列。

2. 定义 Dijkstra 函数

def dijkstra(graph, start):

• graph：加权图，用字典表示，每个键对应一个节点，每个值是一个字典，包含该节点的邻居节点及其权重。
• start：源节点。

3. 初始化距离字典

    distances = {node: float('inf') for node in graph}
    distances[start] = 0

• distances：初始化一个字典，用于存储从源节点到每个节点的最短距离，初始值为无穷大。
• distances[start] = 0：源节点的初始距离为 0。

4. 初始化优先队列

    queue = [(0, start)]

• queue：初始化一个优先队列，存储待处理的节点及其当前距离，初始时将源节点及其距离 0 放入队列。

5. 主循环

    while queue:
        current_distance, current_node = heapq.heappop(queue)

• while queue:：当优先队列不为空时，继续处理。
• current_distance, current_node = heapq.heappop(queue)：从优先队列中取出距离最小的节点及其距离。

6. 检查当前节点的距离

        if current_distance > distances[current_node]:
            continue

• if current_distance > distances[current_node]:：如果当前节点的距离大于 distances 中记录的距离，跳过该节点。

7. 遍历当前节点的所有邻居节点

        for neighbor, weight in graph[current_node].items():
            distance = current_distance + weight

• for neighbor, weight in graph[current_node].items():：遍历当前节点的所有邻居节点及其权重。
• distance = current_distance + weight：计算从当前节点到邻居节点的距离。

8. 更新距离并加入优先队列

            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(queue, (distance, neighbor))

• if distance < distances[neighbor]:：如果计算出的新距离小于 distances 中记录的距离。
• distances[neighbor] = distance：更新 distances。
• heapq.heappush(queue, (distance, neighbor))：将邻居节点及其新距离加入优先队列。

9. 返回结果

    return distances

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

调用 dijkstra 函数计算从节点 'A' 到其他所有节点的最短路径：

distances = dijkstra(graph, 'A')
print(distances)

输出结果：

{'A': 0, 'B': 1, 'C': 3, 'D': 4}

总结

本文详细介绍了 Dijkstra 算法的原理及其 Python 实现。通过理解算法的基本原理和实现细节，我们可以更加灵活地在图论问题中应用 Dijkstra 算法。

---