> 我不会跟大家说我两个月前就写好了，只是今天才发出来。
本文概述
最短路算法，见名知意，就是用于求出图中从某个顶点到另一个顶点最短距离的算法。最短路算法的应用极其广泛。本文将会以求解最短路为中心，围绕着展开叙述一些常见的最短路算法的原理和应用。
根据最短路算法，我们大致地可以将算法分为两大类：
1. 单源最短路径 Single Source Shortest Path：用于快速计算从某一个特定顶点出发到达任意一个点的距离。
2. 多源最短路径 Multiple Source Shortest Path：用于快速计算任意两点之间的最短路径。
本文将会介绍的算法和各算法的特点如下：
1. 深度优先搜索 Depth First Search：单源最短路径算法，可以求解从任意一点开始到另一点的最短路径，但该算法极其耗时。
2. 广度优先搜索 Breadth First Search：单源最短路径算法，仅用于求解无权图。
3. 迪克斯特拉算法 Dijkstra Algorithm：单源最短路径算法，是广度优先搜索算法的加强版。Dijkstra 算法不能处理带有负权边的情况，更不能处理带有负权回路的图。
4. 贝尔曼福特算法 Bellman-Ford Algorithm：单源最短路径算法，可以用于处理又负权边的情况。对其进行队列优化后就变成了我们熟知的 SPFA 算法。
5. 弗洛伊德算法 Floyd Algorithm：多源最短路径算法，基于动态规划思想，能够一次性求出图中任意两点之间的最短路径，但该算法的时间复杂度非常高，达到惊人的 O(N3)O(N^3)O(N3)。弗洛伊德算法能处理带有负权边的情况，但不能处理带有负权回路的图。
为了方便阅读，本文提供的所有代码均会使用 vector 实现的邻接表来存图。
场景引入
在下图中，有 777 条不同的边，每一条路径上方都标记了一个数值 TiT_iTi ，代表通过该条路径所需要的时间。Macw 想知道从 111 号顶点到 555 号顶点所需要花费的最短时间。
不难看出，Macw 所需要花费的最短时间是 141414 分钟，一条可行的方案是从 111 号顶点出发，途径 222，333 号顶点到达顶点 555。虽然人脑可以很快的看出来，但是在庞大的数据量下，人的脑力就显得极其渺小。那对于计算机来说，我们如何能找到一条从 111 号节点到 555 号节点的路径呢？不妨让计算机暴力枚举出所有的可行路径和每条路径分别的耗时，取最小的那一条路径就可以了。深度优先搜索算法是一个选择。
深度优先搜索 DEPTH FIRST SEARCH
如上图所示，从 111 号节点到 555 号节点共有四条路径，每条路径和其分别耗时如下：
1. 1→2→51\to 2\to 51→2→5，耗时 2+16=182 + 16 = 182+16=18 分钟。
2. 1→2→3→51\to 2\to 3\to 51→2→3→5，耗时 2+7+5=142 + 7 + 5 = 142+7+5=14 分钟。
3. 1→4→51\to 4\to 51→4→5，耗时 6+12=186 + 12 = 186+12=18 分钟。
4. 1→4→3→51 \to 4\to 3\to 51→4→3→5，耗时 6+6+5=176 + 6 + 5 = 176+6+5=17 分钟。
其中第二个方案是最优解，耗时 141414 分钟。因此，一个可行的算法方案是使用深度优先搜索暴力枚举出所有可行的路径并记录最小值即可，其代码实现如下：
深度优先嗖嗖算法虽然很有效，但是该算法的运行效率太低下了，只适用于数据量较小的情况。假设图是一个二叉树树形结构，那么在最坏的情况下，这个算法的时间复杂度将会达到 O(2N)O(2^N)O(2N)。当每个顶点的度越多，深度优先搜索算法的时间复杂度就高。因此，在一般情况下，我们不会使用深度优先搜索。
设想在二维 N×MN \times MN×M 地图问题的情况下，我们怎么找到从入口到出口的最佳路径？一般情况下，我们会使用广度优先搜索的算法。广度优先搜索算法的复杂度远远低于深度优先搜索。
广度优先搜索算法 BREADTH FIRST SEARCH
在一个无权图中（或图中所有边的权值均为 111）的情况下，我们会使用广度优先搜索算法来实现。广度优先搜索算法的代码也很简洁：
我们已经知道，在一般的地图问题中广度优先搜索的效率非常高。那我们是否可以加以改进广度优先算法，让它适配带权图呢？答案是可以的，经过改编后的算法就是大名鼎鼎的 Dijkstra 算法。
迪克斯特拉算法 DIJKSTRA ALGORITHM
Dijkstra 算法是一种用于寻找图中从单一源节点到其他所有节点的最短路径的算法（即单源最短路径算法）。它适用于所有边权重为非负值的图。这个算法最早是被荷兰计算机科学家 艾兹赫尔·戴克斯特拉 (Edsger W. Dijkstra) 发明并提出的，因此用他的名字来命名该最短路算法。
Dijkstra 算法的基本思想是逐步扩展最短路径，直到覆盖所有节点。依旧以「场景引入」章节的图来举例子，虽然我们没有办法一下子立刻求解出从 111 号节点到 555 号节点的最短路径，但是如果我们能求出从 111 号节点到 555 号节点所有的前驱节点的最短路径，那么我们就可以立刻计算出从起点到 555 号节点最短路。
如上图所示，555 号节点有三个前驱节点，分别是节点 V={2,3,4}V = \{2, 3, 4\}V={2,3,4}，走到这三个节点的最短距离分别为两分钟、九分钟和六分钟。通过遍历这些前驱节点，我们就可以求出从起点到终点的最短路。显然，对于图中所有的节点，我们都需要按照一定的顺序依次对它们进行相同的操作。这样子，我们就可以求解出从起点开始到图中任意一个点的最短距离了。
Dijkstra 算法具体的实现流程如下：
1. 初始化：
* 创建一个数组，用于记录从源点开始到任意一点的距离。同时设定源节点的距离为 000，其他所有节点的距离为 +∞+\infty+∞ 。
* 将所有节点标记为未访问。
* 使用一个优先队列来存储节点及到某一个节点当前所计算出的最短距离。
2. 选择节点：
* 从未访问的节点中选择当前距离最小的节点作为当前节点。
* PS：如没有特殊情况，一开始这个节点应该是求解最短路问题的起点（起点与自己的距离应该是 000，正如初始化步骤中所提及的）。
3. 更新节点：
* 对于当前节点的每个邻居节点，计算从当前节点到该邻居节点的距离。
* 如果这个距离小于已知的到该邻居节点的距离，则更新该邻居节点的距离。
* 距离更新: 对于每个邻居节点，计算从起点到该邻居节点的距离，如果该距离小于已知的最短距离，则更新最短距离。
4. 标记已访问：
* 将当前节点标记为已访问，表示已经处理完了该节点。
* PS：当节点被标记完已访问后，从起点到该节点的最短距离就已经被正式确定下来了，在后续的计算过程中该节点的距离将不会再被更新。标记节点已访问可以在「选择节点」步骤完成后时就进行。换句话说，第三步和第四步的顺序并不重要。
5. 重复循环：
* 重复上述提到的第 2-4 步，直到所有的点都被标记为已访问。
以下是使用 Dijkstra 算法对例题的模拟过程：
首先初始化距离数组，将源点的距离设置为 000，将除源点以外的所有点的距离设置为 +∞+\infty+∞。正无穷大表示到达该点的最短距离还未知。
从未访问的节点中选择当前距离最小的节点作为当前节点。在一开始，距离最小的节点就是源点本身。如下图，浅绿色表示当前选中的节点，黄色表示该节点的邻居节点。接下来就开始更新两个邻居节点距源点的最近距离。从 111 号点到 222 号点的最短距离为 222，而 222 号节点当前所记录的最短距离是 +∞+\infty+∞，比较发现 2<+∞2 < +\infty2<+∞，因此将 222 号点的距离从原本的正无穷更新为 222。节点 444 也是如此，从起点到该节点的最短路径将由原本的正无穷更新为 666。
此时，111 号节点已经处理完成了，我们将该节点标记为已访问（图中用深绿色表示）。接下来，我们从未访问的节点当中选择一个距离最小的节点作为当前节点。如下图，未访问的节点有 V={2,3,4,5}V = \{2, 3, 4, 5\}V={2,3,4,5}，其当前的距离分别为 Dis={2,+∞,6,+∞}Dis = \{2, +\infty, 6, +\infty\}Dis={2,+∞,6,+∞}，因此我们选择 222 号节点作为新的当前节点，因为该节点是所有未访问节点当中距离源点距离最小的那个节点。
从 222 号节点开始，更新该节点的所有邻居节点。对于 555 号节点，原本的距离是 +∞+\infty+∞，但从源点出发，经过 222 号节点的距离为 2+16=182 + 16 = 182+16=18，显然这个距离比原本的正无穷大更优，因此更新该节点的最短距离为 181818。对于 333 号节点也是如此，从源点出发经过 222 号节点的最短距离是 2+7=92 + 7 = 92+7=9，因此将 333 号节点的距离更新为 999。
将 222 号节点标记为已访问。接下来再从未访问的节点中选择一个距离最近的节点，现在未访问的节点有 V={3,4,5}V = \{3, 4, 5\}V={3,4,5}，其中 444 号节点的距离最短，因此选择 444 号节点作为当前节点。从 444 号节点出发可以到达的节点只有 333 号节点，如果从源点出发经过 444 号节点再到 333 号节点的距离为 6+6=126 + 6 = 126+6=12，这显然比当前 333 号的距离更大，因此这不是一个更优的解，本轮将不再更新 333 号节点的最短距离。
将 444 号节点标记为已访问。现在再从未访问的节点中选择一个距离最小的节点作为当前节点，因此我们将选择 333 号节点作为当前节点。我们发现从源点出发经过 333 号节点到 555 号节点的距离为 9+5=149 + 5 = 149+5=14，这比 555 号节点当前记录的 181818 更优，因此更新 555 号节点的最短距离。
将 333 号节点标记为已访问。
选择 555 号节点作为当前节点。由于 555 号节点没有任何的后继节点，因此循环结束。将 555 号节点标记为已访问。
至此，所有的节点都标记为已访问，Dijkstra 算法结束。此时距离数组记录的值就是从源点出发到各个点的最短距离。
在下方代码中，为了快速的找到当前距离最小的节点，我们将会使用 C++ 自带的优先队列 (Priority Queue) 数据结构来实现。
完整的 Dijkstra 求解最短路的代码如下（对应例题：洛谷 - P4779 【模板】单源最短路径（标准版） 和 ACGO - A569.单源最短路径1）：
由于该算法是基于优先队列实现的，优先队列求出最小值的复杂度为 O(log2(V))O(log_2(V))O(log2 (V))（使用了二叉堆优化），因此 Dijkstra 的时间复杂度约为 O((V+E)×log2V)O((V + E) \times log_2{V})O((V+E)×log2 V)，其中 VVV 代表图中顶点的数量，EEE 代表图中边的数量。相比之下，Dijkstra 算法的运行效率非常优越。该算法也是在求解最短路问题中应用最广泛的算法之一。
贝尔曼福特算法 BELLMAN-FORD ALGORITHM
Bellman-Ford 算法也是一种用于求解单源最短路径问题的算法，特别适用于含有负权边的图。与 Dijkstra 算法不同，Bellman-Ford 算法能够检测到负权重环路的存在。
Bellman-Ford 的算法思想是通过 松弛操作 (Relaxation) 逐步找到从源点到所有其他顶点的最短路径。对一条边进行松弛操作指的是检查一条边/图上的路径是否能提供更短的路径。如果可以，那么就更新答案。
该算法会重复对图中的所有边进行松弛操作，总共执行 ∣V∣−1\lvert V\rvert - 1∣V∣−1 次，其中 ∣V∣\lvert V\rvert∣V∣ 是图中顶点的数量。
Bellman-Ford 算法具体的实现流程如下：
1. 初始化：
* 创建一个数组，用于记录从源点开始到任意一点的距离。同时设定源节点的距离为 000，其他所有节点的距离为 +∞+\infty+∞ 。
2. 松弛操作：
* 对于每一条边 (u,v)(u, v)(u,v)，和这条边的权重 w(u,v)w(u, v)w(u,v)，如果可以使得 disu+w(u,v)<disvdis_u + w(u, v) < dis_vdisu +w(u,v)<disv ，则将 disvdis_vdisv 更新为 disu+w(u,v)dis_u + w(u, v)disu +w(u,v)。其中，disidis_idisi 表示编号为 iii 节点的距离。
* 重复上述步骤 ∣V∣−1\lvert V\rvert - 1∣V∣−1 次。
3. 检测是否存在负环：
* 再次对所有边执行松弛操作。如果发现某条边 (u,v)(u, v)(u,v) 仍能使 disu+w(u,v)<disvdis_u + w(u, v) < dis_vdisu +w(u,v)<disv 成立，则说明图中存在负权重环路。
* 换句话说，如果一个图不存在负环，则这张图的边在经历最多 ∣V∣−1\lvert V\rvert - 1∣V∣−1 次松弛操作后将不能再进行松弛了。
以下是使用 Bellman-Ford 算法对例题的模拟过程：
首先初始化距离数组，将源点的距离设置为 000，将除源点以外的所有点的距离设置为 +∞+\infty+∞。正无穷大表示到达该点的最短距离还未知。
选择一条边，对该边尝试进行一次松弛操作。如下图（红色的边表示当前选中的边），通过这一条边可以将从源点到 222 号点的距离从正无穷大缩短至 222，因此更新新的距离。
以次类推，依次遍历并尝试松弛所有的边。当每一条边经历 ∣V∣−1\lvert V\rvert - 1∣V∣−1 次松弛操作后，算法结束。此时距离数组记录的值就是从源点出发到各个点的最短距离。
完整的 Bellman-Ford 求解最短路的代码如下（对应例题：洛谷 - P4779 【模板】单源最短路径（标准版） 和 ACGO - A569.单源最短路径1，由于标准版的 Bellman-Ford 算法运行效率低下，因此不保证可以通过所有的测试点）：
使用 Bellman-Ford 算法判断负环的方法如下（对应例题：ACGO - A551.单源最短路径2）：
因为 Bellman-Ford 算法要对每条边进行 ∣V∣−1\lvert V\rvert - 1∣V∣−1 次松弛操作，并且还需要判断一次是否存在负环，因此该算法的时间复杂度为 O(V×E)O(V \times E)O(V×E)，其中 VVV 是顶点数，EEE 是边数。Bellman-Ford 的时间复杂度相对来说比较高，因此在没有负环的时候仍然推荐使用 Dijkstra 最短路算法作为首选方案。
SPFA 算法 SHORTEST PATH FASTER ALGORITHM
SPFA (Shortest Path Faster Algorithm) 算法是 Bellman-Ford 算法的改进版本，专门用于加速单源最短路径的计算。该算法通过队列机制减少了不必要的松弛操作，从而提高了代码的运行效率。SPFA算法在实践中表现出优异的性能，特别是在稀疏图中。
SPFA 算法利用一个队列来存储需要松弛的顶点，并且每个顶点在队列中最多出现一次。通过这种机制，SPFA 算法避免了对所有边进行多余的松弛操作，从而提高了效率。
但 SPFA 算法也有缺陷，在一些特殊的情况下，可能会出现卡死的情况（有一句古话：关于 SPFA，它死了）。在最坏的情况下，SPFA 的复杂度高达 O(V×E)O(V\times E)O(V×E)（就是普通 Bellman-Ford）算法的运行效率。但该算法在大多数情况下表现优异，通常情况该算法的平均时间复杂度在 O(V+E)O(V + E)O(V+E) 附近，其中 VVV 是图中顶点的数量，EEE 是图中边的数量。
SPFA 算法具体的实现流程如下：
1. 初始化：
* 创建一个数组，用于记录从源点开始到任意一点的距离。同时设定源节点的距离为 000，其他所有节点的距离为 +∞+\infty+∞ 。
* 初始化一个队列（不需要是优先队列，普通队列即可）。将源点加入到队列之中。
* 初始化一个数组用来记录某个顶点是否在队列之中。在程序开始时，源点应该被标记为已经入队。
2. 松弛操作：
* 对于每一条边 (u,v)(u, v)(u,v)，和这条边的权重 w(u,v)w(u, v)w(u,v)，如果可以使得 disu+w(u,v)<disvdis_u + w(u, v) < dis_vdisu +w(u,v)<disv ，则将 disvdis_vdisv 更新为 disu+w(u,v)dis_u + w(u, v)disu +w(u,v)。其中，disidis_idisi 表示编号为 iii 节点的距离。
* 如果成功进行了松弛操作，且顶点 vvv 不在队列之中，那么将顶点 vvv 加入到队列之中。
3. 重复执行：
* 重复第二部的操作，直到队列为空。
* PS：如果某个点加入了队列 ∣V∣\lvert V\rvert∣V∣ 次，则说明该图存在负环，应该立结束程序。
以下是使用 SPFA 算法对例题的模拟过程：
首先初始化距离数组，将源点的距离设置为 000，将除源点以外的所有点的距离设置为 +∞+\infty+∞。正无穷大表示到达该点的最短距离还未知。同时，将源点加入到队列之中，并将源点标记为已加入队列。
选择队首元素（在当前情况就是 111 号节点），松弛与 111 号节点相邻的两条边。从 111 号节点出发，到 222 号节点和 444 号节点的距离都比正无穷大要小，因此更新这两个节点的距离。与此同时，由于 222 号节点和 444 号节都不在队列中，因此将这两个节点加入到队列。
弹出位于队首的 111 号元素，选择位于队首的 222 号元素，松弛与 222 号节点相邻的两条边。从 222 号节点出发，到 333 号节点和 555 号节点的距离都比正无穷大要小，因此更新这两个节点的距离。与此同时，由于 333 号节点和 555 号节都不在队列中，因此将这两个节点加入到队列。
弹出位于队首的 222 号元素，选择位于队首的 444 号元素，松弛与 444 号节点相邻的两条边。从 444 号节点出发，到 333 号节点和 555 号节点的距离都比原本要远，因此不更新任何节点，也不将任何节点加入到队列当中。
弹出位于队首的 444 号元素，选择位于队首的 333 号元素，松弛与 333 号节点相邻的两条边。从 333 号节点出发，到 555 号节点的距离为 9+5=149 + 5 = 149+5=14，比原本的 181818 要更优，因此更新 555 号节点。但由于 555 号节点已经被加入到了队列之中，因此不再重复加入。
弹出位于队首的 333 号元素，选择位于队首的 555 号元素，由于该节点不存在任何的后继节点，因此不做任何操作，直接将 555 号节点弹出队列。至此，队列为空，SPFA 算法结束。
完整的 SPFA 求解最短路的代码如下（对应例题：洛谷 - P4779 【模板】单源最短路径（标准版） 和 ACGO - A569.单源最短路径1，由于标准版的 SPFA 算法最坏的情况会被卡死，因此不保证可以通过所有的测试点）：
使用该算法判断负环，只需要判断是否存在一个节点被加入了超过 ∣V∣−1\lvert V\rvert - 1∣V∣−1 次即可。完整的 SPFA 判断是否存在负环的代码如下（对应例题：洛谷 - P3385 【模板】负环）：
弗洛伊德算法 FLOYD ALGORITHM
Floyd 算法运用了动态规划的思想，该算法用于求解所有顶点对之间的最短路径问题。Floyd 算法适用于带权有向图，可以处理负权重边，但不能处理图中含有负权重环的情况。
Floyd l算法通过三重循环迭代地更新最短路径。设定一个二维矩阵 DisDisDis，其中 Disi,jDis_{i, j}Disi,j 表示从顶点 iii 到顶点 jjj 的最短路径权重。初始时，将直接相连的顶点的距离设置为边的权重，没有直接连接的顶点距离设为无穷大，顶点到自身的距离设为 000。
该算法的核心思想是，检查每一对顶点 (i,j)(i, j)(i,j) 是否可以通过另一个顶点 kkk（作为中转节点） 使得从 iii 节点到 jjj 节点的路径更优。如果通过 kkk 可以使路径更短，则更新 Disi,jDis_{i, j}Disi,j 。
因此可以得到状态转移方程：Disi,j=min(Disi,k+Disk,j,Disi,j)Dis_{i, j} = \min(Dis_{i, k} + Dis_{k, j}, Dis_{i, j})Disi,j =min(Disi,k +Disk,j ,Disi,j )。
综上所述，Floyd 的代码如下（对应例题：洛谷 - B3647 【模板】Floyd）：
Floyd 算法的时间复杂度在 O(N3)O(N^3)O(N3)，其中 NNN 表示图中顶点的数量。因此该算法的执行效率是极其低的，在没有特殊情况下，尽量避免使用该算法。但如果遇到多源最短路径的题目，Floyd 算法还是首选方案。
DIJKSTRA 算法和 SPFA 算法的主要区别
1. 处理负权边：
* SPFA：可以处理负权边，并且在某些情况下表现出色。SPFA还可以检测负权环。
* Dijkstra：无法处理负权边，因为 Dijkstra 算法假设已经找到的最短路径，且不会被后续路径更新。
2. 队列机制：
* SPFA：使用一个队列来存储需要处理的顶点。顶点可能多次进入队列，但每次只有在更短路径被发现时才重新入队。
* Dijkstra：使用优先队列（通常是最小堆）来存储顶点，以确保每次处理的顶点是当前最短路径确定的顶点。
3. 时间复杂度：
* SPFA：在实际应用中通常表现良好，平均时间复杂度为 O(V+E)O(V + E)O(V+E)，但最坏情况下为 O(V×E)O(V\times E)O(V×E)。
* Dijkstra：使用最小堆实现时，时间复杂度为 O((V+E)×log2V)O((V + E)\times log_2V)O((V+E)×log2 V)。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
本期讲解了常见的几种求解最短路问题的算法，共计 8409 字。谢谢阅读。
