Dijkstra 算法是如何找到最短路径的

Dijkstra 算法是如何找到最短路径的

Dijkstra 算法概述

Dijkstra 算法是一种求解带权图单源最短路径的贪心算法，适用于边权均为非负数的有向图或无向图（可以出现环）。算法从源点出发，为每个顶点维护最短距离：源点设为 0，其余设为无穷大；随后反复从未确定的顶点中选出距离最小者，将其确定，并用经过它的路径来更新邻接边，即判断经过该顶点到达邻点是否能得到更短路径。由于边权非负，一旦某个顶点被选中，它的最短距离便不会再被后续路径改写。循环直到所有可达顶点均被确定，或目标顶点已确定为止。若同时记录每次更新时通过的前驱顶点，则还可以从终点反向还原完整路径，便于输出和测试。

在采用邻接矩阵和顺序查找时，Dijkstra 算法的时间复杂度为 $O(V^2)$；而采用邻接表实现时，时间复杂度为 $O(V+E)$，其中 $V$ 和 $E$ 分别为顶点的规模与边的规模，但常数较大，更适合稀疏图。需要注意的是，Dijkstra 算法不能正确处理负权边，若图中存在负权时应考虑 Floyd 算法。接下来，笔者将以一个非负权边无向联通图为例，来看看 Dijkstra 算法是如何找到某个顶点到其它所有顶点的最短路径的。

工作过程

笔者使用如下的一个非负权边无向联通图，作为演示示例：

若使用邻接矩阵，则可以表示为：

$$ A= \begin{bmatrix} 0 & 2 & 4 & 1 & \infty & \infty\\ 2 & 0 & \infty & 3 & \infty & \infty\\ 4 & \infty & 0 & 2 & 5 & \infty\\ 1 & 3 & 2 & 0 & 2 & 4\\ \infty & \infty & 5 & 2 & 0 & 3\\ \infty & \infty & \infty & 4 & 3 & 0 \end{bmatrix} $$

由于这是一个无向图，因此其邻接矩阵显然满足 $ A=A^T $，并且对角线上元素恒为 0。

挑选源点并初始化

第一步，我们先挑选出发点。笔者想获得的是 C 点到其它所有顶点的最短路径，那么就将 C 点作为源点，之后所有的路径、边权计算都将从 C 点开始。

此时，让我们写一张表格，其中列坐标代表迭代更新的次数，行坐标代表除了 C 点以外的顶点，最后一行写已获得最短路径的顶点的集合：

因为还没有“出发”，因此，我们先将 C 到其它所有顶点的距离初始化为 $\infty$（非负权边不考虑 $-\infty$ 的情况），便于统一后面的更新逻辑。

从 C 点出发

观察该无向图，不难发现，与 C 点邻接的有顶点 A、顶点 D 和顶点 E。因此，C 到上述三个顶点的路径长度分别为 4、2、5；由于我们最开始将 C 点到它们的路径长度初始化为了 $\infty$，而实数 4、2、5 都比 $\infty$ 小，因此第一轮中，我们可以为顶点 A、顶点 D 和顶点 E 找到比之前所记录的更短的路径长度。

但可惜的是，C 点并不邻接顶点 B 和顶点 F，无法直接到达，所以它们的路径长度仍然保持 $\infty$。通过上述的分析与计算，我们可以为表格填入如下数据：

不难发现，从 C 到 D 的路径是第一轮计算中最短的那一个，由于 C 到 D 之间不可能存在比直接 C -> D 边数更多还权值和更小的路径，否则这条“最短路径”就不会被确定下来，因此 C -> D 的最短路径就这样被确定了下来。因此，顶点集合 $S$ 将包含 C 与 D 两个顶点：

重点来了，对于后面的每一轮计算，我们都从上一轮已经获得的最短路径中的最后一个顶点出发，计算与之邻接顶点的路径权值和已有路径的长度之和，并不断挑出每轮的最短路径并重新出发、计算。对于第二轮，由于第一轮的最短路径是 C -> D，那么我们从 C 出发并经过 D，来看看 C -> D 到其它顶点的路径之和分别是多少吧：

与 D 邻接的顶点有 C、A、B、E、F，但由于 C 是源点且为前驱顶点，因此不考虑回到 C 点的路径。计算可得，D 点到顶点 A、B、E、F 的权值分别为 1、3、2、4，再加上原本 C -> D 的路径长度，算得从 C 点出发、经过 D 点到上述四个顶点的路径长度分别为 3、5、4、6。由于在第一轮中，C 到上述四个顶点记录的路径长度分别为 4、$\infty$、5、$\infty$，比较发现第二轮获得的路径长度都比第一轮中所记录的小，因此可以将它们的路径及路径长度做更新，并“记录在案”：

同样，选取第二轮中路径长度之和最小的那条路径序列，也就是 C -> D -> A，基于相同的原理，第二轮即可确定 C 点到 A 点的最短路径，即 C -> D -> A，记入顶点集合 $S$ 中：

自然，后续从 C 点出发，经过 D 点和 A 点计算 B 点的过程也不用多说。但细心的读者肯定在手动模拟后发现，从 C -> D -> A -> B 的路径长度似乎和原来 C -> D -> B 时一样，都是 5。当路径长度总和不变时，既可以保留原来的路径序列，也可以进行更新 —— 反正路径长度没变。但笔者推荐保留原来的路径序列，在顶点数量极多的情况下，实际编程中可以通过 if 语句进行过滤，避免不必要的写操作。

但对于 E、F 点，麻烦来了，A 点压根不邻接 E、F 两点，怎么更新呢？答案是：不用更新。由于在本轮路径探测中，A 点并不直通 E、F，所以本轮中由 C -> D -> A 到 E、F 的路径计算就是 $\infty$。从表格可以知道，第二轮中 C 到 E 与 C 到 F 所存在的路径长度分别是 4 和 6，而本轮却计算得到两个 $\infty$，还不如第二轮获得的结果，因此保留第二轮计算获得的路径序列和长度，让它们俩继续沉淀一下：

C -> D -> E 是第三轮中获得的最小的路径长度序列，那么第三轮确定的顶点则是顶点 E：

后面的过程就都大同小异了，若您前面已充分理解了 Dijkstra 算法和贪心的思想，相信后面的计算、更新和最短路径确定过程您将可以对照图示和表格自行手动模拟出来：

对于 C -> D -> E，有：

对于 C -> D -> B，有：

到了第六轮，经过检查，发现顶点集合中已经包含了所有的顶点，意味着从 C 出发到其它所有顶点的最短路径长度都已经确定，至此，Dijkstra 算法运行结束。

于是我们获得了从 C 点到 A、B、D、E、F 顶点的最短路径，分别是 3、5、2、4、6。各位读者可以手动验证一下，通过 Dijkstra 算法获得的单源最短路径是否和“瞪眼法”找出来的最短路径一样。

总结

通过本文的示例，Dijkstra 算法并不需要穷举源点到各顶点的全部路径，而是将顶点分为“最短距离已确定”和“最短距离待确定”两类。算法每轮从待确定顶点中选出当前距离最小者，再以它为中间点更新相邻顶点的距离。由于图中不存在负权边，已经确定的最短距离不会在后续计算中被更小的值替代，因此算法能够按照由近及远的顺序逐步得到正确结果。在所用本文的无向图中，以 C 为源点，最终可得到 C 到 A、B、D、E、F 的最短距离分别为 3、5、2、4、6；若同步保存每个顶点的前驱，还能还原对应的完整路径。实际编程时，通常使用距离数组、已访问集合和前驱数组保存状态。邻接矩阵实现简单，但时间复杂度为 $O(V^2)$；对于稀疏图，可使用邻接表和优先队列提升效率。需要牢记的是，Dijkstra 算法成立的前提是所有边权非负，遇到负权边时应改用 Floyd 等其它算法。理解“选出当前最近顶点”和“减量更新相邻边（即所谓的‘松弛’）”这两个步骤，也就掌握了该算法的核心。若您对 Dijkstra、A* 算法和 Floyd 算法的原理或实现有其他看法，欢迎在评论区留言分享！