Dijkstra 算法

1. 什么是 Dijkstra 算法？

Dijkstra 算法由荷兰计算机科学家 Edsger W. Dijkstra 在 1956 年提出，旨在解决 单源最短路径 问题。该算法广泛应用于路由、图像处理等领域。

2. Dijkstra 基本原理

用坐地铁的方式比喻

找到从你家附近的地铁站到某个目的地的最快路线。Dijkstra 算法逻辑如下：

1. 初始化：

   • 你拿到了一张地铁地图，上面标有所有地铁站（节点）和它们之间的线路（边），每条线路的行车时间（权重）。
   • 你把自己所在的地铁站（起点）的时间标记为 0，其他所有站点的时间暂时标记为 ∞，表示还不知道怎么过去。

2. 选择当前最近的站点：

   • 你查看所有已经记录的站点，找到乘车时间最短的那个，比如 A（你当前的站点）。
   • 你看看从 A 直接可以到达哪些站，比如 B 和 C。

3. 更新最快路线：

   • 计算 A -> B 和 A -> C 所需的时间。
   • 如果发现去某个站的新路线比之前记录的更快，就更新它的最快时间。
   • 例如，如果 A -> B 需要 1 分钟，A -> C 需要 4 分钟，那么更新到 B 的时间为 1 分钟，到C 的时间为 4 分钟。

4. 继续扩展：

   • 你再次选择当前已知最快的站点，比如 B。
   • 你看看 B 可以到达哪里，比如 C 和 D，然后尝试更新 C 和 D 的最快时间。
   • 例如，如果 B -> C 需要 2 分钟，那么 A -> B -> C 总共是 1 + 2 = 3 分钟，比 A -> C 直接过去的 4 分钟 更快，所以更新 C 的时间为 3 分钟，最短路径为 A -> B -> C。

5. 重复这个过程，每次选择当前已知最快的站点去扩展，直到所有的站点都计算完毕。

3. 代码实现

下面是 Python 版本的 Dijkstra 算法：

import heapq

def dijkstra(graph, start):
    # 初始化：所有点的最短距离设为无穷大，起点设为 0
    shortest_paths = {node: float('inf') for node in graph}
    shortest_paths[start] = 0
    pq = [(0, start)]  # (当前已知的最短距离, 节点)
    
    while pq:
        current_distance, current_node = heapq.heappop(pq)  # 取出当前距离最短的节点
        
        if current_distance > shortest_paths[current_node]:
            continue  # 如果当前节点的距离已经被更新过，就跳过
        
        for neighbor, weight in graph[current_node].items():
            distance = current_distance + weight  # 计算从当前节点到邻居的距离
            
            if distance < shortest_paths[neighbor]:  # 发现更短的路径
                shortest_paths[neighbor] = distance  # 更新距离
                heapq.heappush(pq, (distance, neighbor))  # 把这个邻居加入队列
    
    return shortest_paths

    '''
    # 地铁拓扑图
         A
       /   \
      1      4
     /        \
    B ---2--- C
     \       /
      5     1
       \   /
         D
    '''

# 拓扑图用 json 表示
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' 开始的最短路径
shortest_paths = dijkstra(graph, 'A')
print(shortest_paths)

4. 为什么使用 heapq？

在 Dijkstra 算法中，我们需要不断找到当前最短路径的节点并更新邻居的路径，这里就用到了 heapq（最小堆）。

• heapq.heappop(pq)：每次取出当前已知的最短路径节点。
• heapq.heappush(pq, (distance, neighbor))：发现更短路径时，把 (新的距离, 邻居) 放入堆。

heapq 的作用示例

pq = [(3, 'C'), (1, 'B'), (4, 'D')]
heapq.heapify(pq)  # 让它变成最小堆
print(heapq.heappop(pq))  # 取出 (1, 'B')，因为 1 是最小的

为什么 heapq 更快？

如果用普通列表找最短路径：

• 找最小值：需要 O(n) 遍历所有节点。
• 更新列表：插入新路径可能也要 O(n)。

但 heapq 维护最小堆，保证堆顶始终是最短路径，时间复杂度：

• 取最小值（heappop）：O(log n)。
• 插入新路径（heappush）：O(log n)。

所以 Dijkstra 算法的总复杂度是 O((V + E) log V)，比普通实现快很多！🚀

5. 结果解释

执行后，代码会输出从 A 到其他点的最短路径，例如：

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

• A -> B：最短路径是 1 分钟
• A -> C：最短路径是 A -> B -> C，需要 3 分钟
• A -> D：最短路径是 A -> B -> C -> D，需要 4 分钟