Dijkstra 算法详解：原理、代码与复杂度

Dijkstra 算法解决什么问题

广度优先搜索找的是边数最少的路径，但现实中的道路、网络链路和航班，长度、费用或延迟各不相同。Dijkstra 算法解决的是此类带权图上的单源最短路径问题：给定起点，求到其余每个节点的最小总代价，以及对应的路径。

Edsger W. Dijkstra 于 1959 年在论文《A note on two problems in connexion with graphs》中发表了该算法。

用大白话讲思路

1. 把起点的距离设为 0，其余所有节点的距离设为无穷大。
2. 选出距离最小的未确定节点，它的距离此时即为最终值。
3. 松弛每条权为 w 的出边 u → v：如果 dist[u] + w < dist[v]，就令 dist[v] = dist[u] + w，并记录 u 为 v 的父节点。
4. 重复第 2、3 步，直到所有可达节点都已确定。

为什么最小距离就是最终值？到达该节点的其他路线，必须经过某个距离不小于它的节点，而在权非负的情况下，后续的边只会增加代价。

逐步演示一个例子

有向图的边为 A→B（4）、A→C（1）、C→B（2）、B→D（1）、C→D（5）、D→E（3），从 A 出发。

B 起初通过直接边得到距离 4，随后经 C 改进为 3。到 E 的最短路径是 A → C → B → D → E，总代价为 1 + 2 + 1 + 3 = 7。

使用 heapq 的 Python 实现

Python 的 heapq 模块提供二叉最小堆。它没有“减小键值”操作，所以每当距离被改进，就压入一个新的 (distance, node) 对，并在弹出时跳过过时的条目。这称为惰性删除。

import heapq
def dijkstra(graph, start):
    dist = {start: 0}
    parent = {start: None}
    heap = [(0, start)]
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue                      # outdated entry
        for v, w in graph[u]:
            nd = d + w
            if nd < dist.get(v, float("inf")):
                dist[v] = nd
                parent[v] = u
                heapq.heappush(heap, (nd, v))
    return dist, parent
graph = {
    "A": [("B", 4), ("C", 1)], "B": [("D", 1)],
    "C": [("B", 2), ("D", 5)], "D": [("E", 3)], "E": [],
}
dist, parent = dijkstra(graph, "A")
print(dist)  # {'A': 0, 'B': 3, 'C': 1, 'D': 4, 'E': 7}

若要得到到某个目标的路径，沿着父节点链接回溯到起点：

def path_to(parent, target):
    path = []
    while target is not None:
        path.append(target)
        target = parent[target]
    return path[::-1]
print(path_to(parent, "E"))  # ['A', 'C', 'B', 'D', 'E']

如果只需要到某一个目标的距离，那么目标从堆中弹出的那一刻就可以停止，因为此时它的距离已经是最终值。

时间与空间复杂度

空间复杂度为 O(V + E)，用于存放图、距离与父节点映射以及堆。

变体与常见错误

• 漏写 if d > dist[u]: continue 检查并不会出错，但算法会处理过时条目，可能慢很多。
• 只压入节点而不是 (distance, node)，会让堆的顺序失去意义。
• 如果节点是无法比较的对象，距离相同时 heapq 会去比较节点本身并抛出 TypeError。请压入带唯一计数器的 (distance, counter, node)。
• A* 搜索就是在优先级中加入启发函数的 Dijkstra；当你对剩余距离有较好的估计时，它探索的节点更少。
• 双向 Dijkstra 同时从起点和终点出发搜索，两路相遇时停止。

何时使用及实际应用

• 路由：OSPF、IS-IS 等链路状态路由协议所用的最短路径优先（SPF）计算就基于 Dijkstra 算法。
• 地图与导航：实际系统会在 Dijkstra 式搜索之上加入预处理。
• 面试题：网络延迟时间、最便宜航班（带中转次数限制）、网格中的最小体力路径，以及图上一切“最小总代价”问题。