Dijkstra 算法详解：分步讲解

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

什么是 Dijkstra 算法？

Dijkstra 算法由 Edsger W. Dijkstra 于 1959 年提出，它在带权图中找到从单一源点到其余每个节点的最短路径。它对有向图和无向图都适用，但有一个硬性条件：每条边的权必须非负。

把图想象成一张路网。节点是路口，边是道路，每个权重是走这条路所需的时间或距离。Dijkstra 算法回答了每个导航应用都会问的问题：从我所在的位置到其他所有地方，最快的路线是什么？它是最短路径算法这一更大家族中的一员，也是图论学习路线图中的常客。

核心思想

Dijkstra 算法是贪心的。它为每个节点保存一个暂定的最短距离，并重复一个简单的动作：

总是访问已知距离最小的未访问节点，然后用它来改进它的邻居。

使其正确的洞见是：因为所有权都非负，一旦你选出最近的未访问节点，之后就不可能有任何路径以更低代价到达它。所以某个节点被选中的那一刻，它的距离就是最终的。这一条保证就是整个算法。

具体来说，算法维护：

• 到每个节点的一个距离，除源点为 0 外，其余都从无穷大开始。
• 一个优先队列（最小堆），总是返回最近的未访问节点。
• 一组最短距离已确定的最终节点。

改进一个邻居称为松弛：如果经过当前节点的路径比邻居已记录的距离更短，就把它调低。

它如何运作，分步讲解

让我们在这张带权图上从节点 A 运行 Dijkstra。蓝色的边将构成最终的最短路径树，每个节点旁边的数字是它从 A 出发的最终最短距离。

下面是执行过程。每一步我们确定最近的未访问节点（加粗），并松弛它的邻居。∞ 表示"尚未到达"。

注意第三步：访问 C 把 B 从 4 降到了 3，因为路线 A → C → B（2 + 1）胜过直接边 A → B（4）。这就是松弛在起作用。在实时图上看它展开会让这个套路瞬间清晰，你可以在算法可视化工具中做到这一点。

Python 实现

这份干净、可用于面试的版本用 Python 的 heapq 作为优先队列。图是一个邻接表，把每个节点映射到一列 (邻居, 权重) 对。

import heapq

def dijkstra(graph, start):
    # 除源点外，每个节点都从无穷远开始。
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    pq = [(0, start)]  # (目前的距离, 节点)

    while pq:
        dist, node = heapq.heappop(pq)

        # 对已确定节点的一个过时且更长的条目：跳过。
        if dist > distances[node]:
            continue

        for neighbour, weight in graph[node]:
            new_dist = dist + weight
            # 松弛：找到了到达邻居的更便宜路径。
            if new_dist < distances[neighbour]:
                distances[neighbour] = new_dist
                heapq.heappush(pq, (new_dist, neighbour))

    return distances

有两个细节很重要。第一，我们压入一个新条目，而不是原地更新堆，然后用 dist > distances[node] 检查来跳过过时条目。这种"惰性删除"让代码保持简单，也是标准做法。第二，算法天然会计算到所有节点的距离；若想在单一目标处提前停止，一取出它就返回即可。

时间与空间复杂度

开销取决于优先队列。每条边至多触发一次压入，而二叉堆上的每次压入或弹出耗费 O(log V)。

空间为 O(V)，用于距离表加上队列。这些上界背后的推理，以及它们在所有图算法之间的比较，参见图算法复杂度指南和一页纸的速查表。

Dijkstra 何时失效：负权

贪心的保证完全建立在非负权之上。加入一条负边，整件事就可能崩塌。

假设算法把某个节点定为最终，因为它看起来最近，距离为 5。之后它发现一条看似更长的路线，经过一条 -4 的边，实际上以 3 到达该节点。太晚了：Dijkstra 已经把 5 宣布为最终并继续前进。答案是错的。

要记住的规则：非负权，用 Dijkstra。只要有负权，就用 Bellman-Ford，它反复松弛每条边，还能检测负环。

Dijkstra 与其他算法的对比

Dijkstra 只是众多工具之一。选对哪一个归根结底取决于图。

最近的亲戚是 A* 搜索，也就是 Dijkstra 加上一个把搜索导向单一目标的启发式。而 Dijkstra 本身其实就是把普通队列升级为优先队列的广度优先搜索。

现实应用

• 导航与地图：两地之间最短或最快的路线，最经典的用途。
• 网络路由：诸如 OSPF 的链路状态协议用 Dijkstra 计算转发表。
• 游戏与机器人：地图上的移动代价，通常在其上叠加 A*。
• 运营与物流：供应、电信和交通网络中的最小代价路径，是运筹学的常备工具。