这篇文章上次修改于 260 天前，可能其部分内容已经发生变化，如有疑问可询问作者。

ACM程序课算法笔记10——最短路径问题

松弛

最短路算法中，松弛是最关键的思想，彻底的理解松弛，就能理解最短路径的算法。

以下是边的松弛，而且是有向边的松弛。

void relax(WeightedDigraph G, Edge e)
{
    int from = e.from;
    int to = e.to;
    if (distTo_[to] > distTo_[from] + e.weight)
    {
        distTo_[to] = distTo_[from] + e.weight;
        edgeTo_[to] = e;
    }
}

意思就是，看看这个有向边，能否为最短路结果提供贡献，如果可以，那么就使用它。

通过这个思路，我们可以知道由于每次贡献都会让最短路结果更小，所以考虑的最短路只会变小不会变大。

以下不同的算法，均利用了松弛，主要思想也是松弛，不同点在于目的，和对松弛边的顺序不同。

松弛的distTo数组就是动态规划的体现。

Dijkstra算法

结果

获得到了指定起始点到所有点的距离长度。

简述算法

算法依照逐渐考虑边的形式来解决，主要思想在于松弛

松弛顺序：

先松弛起点
再松弛没有松弛过的离起点最近的点

松弛完所有的点就结束了

分析

Dijkstra实际上是贪心+动态规划的算法。

根据松弛，就是DP。然而根据每次选择最近的点进行松弛，就是贪心。

理解贪心的合理性：

如果我们不按照贪心的顺序进行松弛点，当在松弛一条边的时，distTo[to]和 distTo[from]如果都是INF，那么这个松弛就是无效的，因为无法做出任何贡献，如何让松弛有效成为最大问题：

松弛有效的前提是，distTo[from]已经是最小的了，这就是Dijkstra的贪心体现。

先松弛起点，所有的distTo中最小的，就已经是这个点的答案了，因为其他的路径必须要从其它点路过其它点的距离已经远于最小的了，最小点也就是答案了。

同时我们顺手理解了另外一个问题Dijkstra算法不能处理负边，因为我们保证最小点也就是答案，这是松弛有效的前提，最小点是答案的前提是其他的路径从其它点路过，其它点因为更大所以不会影响最小点，但如果有负边，就不一样了。

Dijkstra算法基于优先队列优化

结果

依旧是获得到了指定起始点到所有点的距离长度。

简述算法

依旧在于松弛的顺序，用优先队列(最小堆)维护distTo，每次松弛距离最小的点即可。

分析

上述Dijkstra算法说过，每次选择最近的点，也就是每次都找dist里面最小距离的点，至于这种经常更新，还要找到最小点的过程，我们就可以用队列进行优化。否则要每次遍历一遍这个数组去找到最小的点。

Floyd算法

结果

获得到了所有的两个点之间的最小路径

简述算法

Floyd算法的主要思想是逐步地更新这个二维数组，通过考虑从中间节点经过的路径来找到更短的路径。具体来说，算法的步骤如下：

将dist[i][j]初始化为直接连接节点i和节点j的边的权重。如果两个节点之间不存在直接的边，则将dist[i][j]初始化为一个无穷大的值。
对于每对节点(i, j)，以及每一个可能的中间节点k，检查路径i->k->j是否比当前已知的路径i->j更短。如果是，则更新dist[i][j] = dist[i][k] + dist[k][j]。
重复步骤2，对于每一个可能的中间节点k，直到没有节点可以通过路径i->k->j获得更短的路径为止。

分析

十分暴力的思路，因此为了便于理解，有人又称其为插点法，对于每个点，考虑它会不会成为图中所有点对中的任意两点的中间者。

Bellman-Ford算法

结果

获得到了指定起始点到所有点的距离长度。

简述算法

对所有边进行n - 1次松弛。

分析

Dijkstra为了松弛的有效性，选择按照贪心的顺序去松弛。Bellman-Ford算法为了有效性就比较暴力了，因为无效的松弛不会影响最终结果，该算法决定一次松弛所有边，这样做n - 1次，所有的边都被有效松弛了。

解释：

如果没有负边，已知Dijkstra是有效的，松弛所有边，和起点相关的边被有效松弛，再松弛所有边，和Dijkstra计算的第二个点的所有边都是有效松弛的，以此类推，有n - 1个点，就进行n - 1次全松弛即可。

可处理负边：

Bellman-Ford算法缺点是效率低下，但不同于Dijkstra算法，它可以处理负边。

我们换一个思路，如果一条路径被发现，那么也就是这条路径上所有的边都已经被松弛，对于这条路径，我们假设有起点和终点，从起点开始到终点的顺序逐步松弛边是有效的，无论有没有负边，这个情况都是成立的。

再看，对于一条路径来说，最多有n - 1 条边，每次松弛至少会让一条边有效松弛，重复 n - 1次，这个路径上的所有边就都会被有效松弛了。所以起点的所有路径都被有效松弛了。

负环：

如果一旦出现负环，显然无法进行最小路径的计算，因为程序可以一直在负环绕圈圈，导致最后的结果就是负无穷，然而Bellman-Ford算法可以处理负环。

根据上一个结论，V - 1次全边松弛可以让所有点都有效松弛，因此第V次松弛必定是全无效松弛，然而，一旦出现负环，就可以无限有效松弛下去。如果第V次出现有效松弛，那么必定就有负环了。

Bellman-Ford算法基于队列优化

SPFA

结果

还是获得到了指定起始点到所有点的距离长度。

简述算法

使用一个队列，一轮松弛过后，如果有点的距离发生改变，这个点就要被之后松弛，使用队列记录他，如果这个点还在队列里，就不需要再添加进去了，因此还需要记录是否在队列里。

分析

这个队列只是用于记录要松弛的点而已，并不需要优先队列来找最小。只起到了记录的作用。

所以用栈也行

在队列优化版本中，只有那些在上一轮松弛中发生了变化的节点才会被考虑。这样一来，可以避免对所有边进行松弛。如果上次松弛中，节点没有变化，那么下一步松弛就对它没有任何作用了。

就像上面说明的一样对于一条路径，需要从左往右的逐步松弛，所以一个最有效松弛的前提条件就是，前面一个点的距离发生了变化。把这个作为约束条件，可以大大减少不必要的松弛

注意：一个点可以被重复松弛

负环：

基于队列优化的Bellman-Ford算法，只需要记录所有点松弛的次数，一旦次数大于等于点的个数，就可以代表有负环了。

菊花图是这个算法的弱点，因为会往队列里面加很多的点。

Johnson 全源最短路径算法

Dijkstra 的效率十分优秀，但Dijkstra不能处理带负权的边，我们尤为对Dijkstra感到遗憾。

负权导致贪心失效，我们能不能找到一种方法，让负边变成一种新的形式。而使得Dijkstra合法。

一个直接的想法就是能否让所有边权加上一个固定值，只是不行的，对于两条路径，它们会分别增加边的数量 * 固定值。这是不相等的。

简述算法

创建一个虚拟点x，连接x到所有的点连接一条权为0的边。

使用SPFA计算x到所有点的最短路径（注意有负权边，所以不一定为0）为 H[ i ]

对于一条从 u 到 v 点，边权为 w 的边，设置为 w + H[u] - H[v]

以每个点作为起点跑n轮Dijkstra即可获得任意两点的最短路径。

分析

在这个算法中，算法将H[ i ] 称作 i 点的势能。

我们先要了解关于势能的相关性质。

性质1

对于起点S到终点T，s - p1 - p2 - p3 - p4 - p5 - … - t

= w(s, p1) + w(p1, p2) +… + w( …, t) + H[s] - H[t]

可得变化后的图，对于两个点，不同的路径的两个势能值是一样的。

所以，在变化后的图所找到的最短路径就是原图的最短路径。

性质2

新图中所有的边权非负

因为保证了H[v]是x最短路径，易得H[v] ≤ H[u] + w(u, v)

易得新权值必定不是负。

Mai Icy