Dijkstra 算法——最短路径一步一步讲解

Dijkstra 算法用于在带权图中，从一个起始节点出发找到最短路径，前提是每条边的权重都非负。如果你只关心某一个终点，那么一旦该终点被确定，就可以停止。

它的核心是贪心策略：每一步都从当前已知距离最小、但尚未确定的节点继续扩展。这个做法只有在边权非负时才成立。

Dijkstra 算法解决什么问题

当图的边上带有代价，而你想找到总代价最小的路线时，就可以使用 Dijkstra 算法。这个代价可以表示距离、旅行时间、能量消耗，或者任何你想最小化的量。

它既适用于有向图，也适用于无向图。关键条件很明确：每条边的权重都必须至少为 $0$。

算法是如何工作的

每个节点都维护一个从起点出发的暂定距离。开始时，起点的距离是 $0$，其他所有节点的距离都是 $\infty$。

然后重复下面这个循环：

1. 选出未确定节点中暂定距离最小的那个。
2. 检查通过该节点能到达的每个相邻节点。
3. 如果新路线更便宜，就更新相邻节点的距离。
4. 将当前节点标记为已确定。

第 3 步叫作松弛。一个已确定的节点表示处理完成：在图中不存在负边权的前提下，它的最短距离已经最终确定。

Dijkstra 算法一步一步讲解

下面是完整过程的简洁版：

1. 选择一个起点节点。
2. 将它的距离设为 $0$，其余所有距离设为 $\infty$。
3. 选出未确定节点中暂定距离最小的那个。
4. 松弛它的出边。
5. 将该节点标记为已确定。
6. 重复，直到所有可达节点都已确定；如果你只关心某个目标节点，那么当它被确定时就可以停止。

如果你还记录了每次更新是由哪个前驱节点造成的，那么你不仅能得到最终距离，还能还原出实际路径。

最短路径示例

假设图中有如下边权：

• $A \to B = 4$
• $A \to C = 1$
• $C \to B = 2$
• $B \to D = 1$
• $C \to D = 5$

我们要找从 $A$ 到 $D$ 的最短路径。

初始状态为：

$$\text{dist}(A)=0,\quad \text{dist}(B)=\infty,\quad \text{dist}(C)=\infty,\quad \text{dist}(D)=\infty$$

先确定 $A$，并松弛它的边：

$$\text{dist}(B)=4,\quad \text{dist}(C)=1$$

此时未确定节点中距离最小的是 $C$，所以下一步确定 $C$。

经过 $C$：

• 经过 $C$ 到达 $B$ 的路径代价是 $1+2=3$，比原来的 $4$ 更小，所以更新 $\text{dist}(B)=3$。
• 经过 $C$ 到达 $D$ 的路径代价是 $1+5=6$，所以设定 $\text{dist}(D)=6$。

现在 $B$ 的未确定距离最小，因此确定 $B$。

经过 $B$，到达 $D$ 的路径代价是：

$$3+1=4$$

这比 $6$ 更小，所以将 $\text{dist}(D)$ 从 $6$ 更新为 $4$。

现在 $D$ 是未确定节点中距离最小的。确定它，然后停止。

最短路径是：

$$A \to C \to B \to D$$

总代价为：

$$1+2+1=4$$

这个例子展示了一个关键模式：一开始看起来更差的路线 $A \to B$，后来通过 $C$ 反而变得更优。只要 $B$ 还没有被确定，Dijkstra 算法就允许这种更新。一旦某个节点被确定，它的距离就不会再改变。

为什么非负边权很重要

假设当前未确定节点中最便宜的那个距离为 $d$。以后如果还能找到一条通向它的新路径，那么这条路径一定来自另一个未确定节点，而那个节点的暂定距离至少也是 $d$，再加上一条权重至少为 $0$ 的边。

因此，这条后来出现的路径不可能比 $d$ 更小。这就是为什么在所有边权都非负时，优先确定当前最小暂定距离是安全的。

如果存在负边，这个论证就失效了。现在看起来代价较高的路径，之后可能因为负边而变得更便宜，这意味着过早确定某个节点会得到错误答案。

Dijkstra 算法的常见错误

在存在负边时使用它

哪怕只有一条负边，也会破坏这种贪心逻辑。如果图中可能出现负权重，就应该使用其他最短路径算法。

把“已访问”当成“已完成”

一个节点即使已经有了暂定距离，也不代表它已经处理完成。只有已确定的节点，它的最短距离才是最终结果。

忘记记录前驱节点表

距离只能告诉你代价是多少。如果你还想知道具体路线，就要记录每个距离最后一次被哪个节点更新。

Dijkstra 算法的应用场景

当一个问题可以建模为：在带有非负代价的图中移动时，就可以使用 Dijkstra 算法：

• 地图上的路径规划
• 网络路由
• 带权网格中的机器人运动
• 移动代价不同的游戏寻路

它也是贪心算法中的经典例子，因为它的正确性依赖于一个非常精确的条件。

试着做一道类似题

画一个有五个节点、边权都为正的图，然后手动用距离表运行 Dijkstra 算法。如果你想继续练习，可以自己再设计一个新图，并仔细检查每个节点究竟是在什么时候可以安全地被确定。