Question

用途

一张有向图，选定一个起点，找出起点到图上各点的最短路径，即是找出其中一棵最短路径树。可以顺便侦测起点是否会到达负环，然后找出其中一只负环。

此演算法曾由西南交通大学段凡丁《关于最短路径的 SPFA 快速算法》重新发现，于是中文网路出现了 Shortest Path Faster Algorithm, SPFA 的通俗称呼。学术上查无此称呼，请勿滥用。

想法

当最短路径只有正边和零边，截去末端之后，仍是最短路径，而且长度一定更短。当有负边，长度不会更短，反而更长。

图上有负边，则无法使用 Label Setting Algorithm。受到负边影响，不能先找最短的那一条最短路径。当下不在树上、离根最近的点，以后不见得是最短路径。

图上有负边，就必须使用 Label Correcting Algorithm。就算数值标记错了，仍可修正。

由起点开始，不断朝邻点拓展，不断修正所有邻点的最短路径长度，其中必然涵盖到最短路径树的点与边。拓展过程当中，儘管无法确定最短路径树的长相，但是可以确定最短路径树正在一层一层生长。

一条最短路径顶多 V-1 条边，一棵最短路径树顶多 V 层。拓展邻点 V-1 层之后，必能完成最短路径树。

演算法：找出一棵最短路径树

令 w[a][b]是 a 点到 b 点的距离（即是边的权重）。
令 d[a]是起点到 a 点的最短路径长度，起点设为零，其他点都设为无限大。

一、把起点放入 queue。
二、重複下面这件事，直到 queue 没有东西为止：
　甲、从 queue 取出一点，作为 a 点。
　　　加速：如果 queue 已有 parent[a]，则捨弃 a 点并且重取。
　乙、找到一条边 ab：d[a] + w[a][b] < d[b]。
　丙、以边 ab 来修正起点到 b 点的最短路径：d[b] = d[a] + w[a][b]。
　丁、把 b 点放入 queue。
　　　加速：如果 queue 已有 b 点，则不放。

Single Source Shortest Paths: Bellman-Ford Algorithm

演算法：找出一棵最短路径树

Label Correcting Algorithm 的平行化版本。

图上所有点同时（或依序）修正邻点的最短路径长度，重覆 V-1 次。如此一来就省去了 queue。

令 w[a][b]是 a 点到 b 点的距离（即是边的权重）。
令 d[a]是起点到 a 点的最短路径长度，起点设为零，其他点都设为无限大。

一、重複下面这件事 V-1 次：
　甲、穷举边 ab：d[a] + w[a][b] < d[b]。
　乙、以边 ab 来修正起点到 b 点的最短路径：d[b] = d[a] + w[a][b]。
　　　（即是图上所有边同时进行 relaxation。）

虽然时间複杂度与 Label Correcting Algorithm 相同，但是执行速度比较慢。

Single Source Shortest Paths: Randomized Label Correcting Algorithm

想法：化整为零

Label Correcting Algorithm 的随机化版本。

先前介绍 relaxation 说到：不断寻找捷径以缩短原本路径，终会得到最短路径。

一条捷径如果很长，就不好办了。一条捷径如果很长，可以拆解成一条一条的边，一一尝试以这些边作为捷径。

由于不知道捷径在哪裡，所以只好不断重複尝试图上每一条边，逐步修正最短路径长度，一条一条的边总有一天将会连接成一条完整的捷径。

Label Setting Algorithm 只有正边、零边，知道 relaxation 的正确顺序，逐步设定每个点的最短路径长度。

Label Correcting Algorithm 受负边影响，不知道 relaxation 的正确顺序，只好不断寻找捷径、不断修正每个点的最短路径长度，直到正确为止。

演算法

令 w[a][b]是 a 点到 b 点的距离（即是边的权重）。
令 d[a]是起点到 a 点的最短路径长度，起点设为零，其他点都设为无限大。

一、重複下面这件事：
　甲、找到一条边 ab：d[a] + w[a][b] < d[b]。
　乙、以边 ab 来修正起点到 b 点的最短路径：d[b] = d[a] + w[a][b]。

Single Source Shortest Paths in DAG: Topological Sort

演算法

有向无环图（Directed Acyclic Graph, DAG）只朝一个方向前进，可以依序实施 relaxation，也就是以拓朴顺序实施 relaxation。

此问题类似“ Activity on Edge Network ”，演算法是 Topological Sort 与 Dynamic Programming。

时间複杂度

时间複杂度约是两次 Graph Traversal 的时间複杂度。图的资料结构为 adjacency matrix 的话，便是 O(V^2)；图的资料结构为 adjacency lists 的话，便是 O(V+E)。

找出一棵最短路径树

Single Source Shortest Paths: Yen's Algorithm

有向图可以拆解成一群自环与两个 DAG

索引值一样、索引值从小往大 D+、索引值从大往小 D-。自由调整索引值，得到不同的拆法。

演算法

检查自环是否为负环。若是，演算法结束；若否，自环不影响最短路径，捨弃之。

每回合先算 D+、再算 D-，依照拓朴顺序 relaxation，总共 V/2 回合。时间複杂度是 O(V/2 * 2(V+E)) = O(VE)。

一条最短路径，长度最多 V-1。最佳情况是清一色 D+或 D-，仅一回合。最差情况是 D+和 D-交错出现，需要 V/2 回合。

随机重排索引值、随机重制 D+和 D-，可以避免最差情况，平均 V/3 回合。但是我不会证明，请见：

http://11011110.livejournal.com/215330.html

All Pairs Shortest Paths: Floyd-Warshall Algorithm

用途

一张有向图，找出所有两点之间的最短路径。

演算法：找出所有两点之间最短路径

就只是把“ Warshall's Algorithm ”套用在最短路径问题上面罢了。

d(i, j, k) = min( d(i, k, k-1) + d(k, j, k-1), d(i, j, k-1) )
                  ^^^^^^^^^^^^^^^^^^^^^^^^^^^  ^^^^^^^^^^^^
                  经过第 k 点                    没有经过第 k 点

d(i, j, k)：由 i 点到 j 点的最短路径长度，当第 k 点加入为中继点的时候。

时间複杂度是 O(V^3)，空间複杂度是 O(V^2)。由于计算顺序以及最小值运算的关係，记忆体得以重複使用，只需要二维阵列。

All Pairs Shortest Paths: Johnson's Algorithm

用途

一张有向图，找出所有两点之间的最短路径。

Johnson's Algorithm 首先重新调整边的权重为非负数，顺便检查图上是否有负环，接著放心的使用 Dijkstra's Algorithm 计算所有两点之间的最短路径。

重新调整权重

如何调整权重，才不会影响最短路径、负环的位置呢？

这裡介绍一个巧妙的方法：首先图上每一个 x 点都设定一个权重 h(x)，然后将一条由 i 点到 j 点的边的权重 w(i, j)，重新调整成 w'(i, j) = w(i, j) + h(i) - h(j)。

首先看看路径。图上的一条路径 s~t，权重变成了：

  w'(s~t)
= w'(sab…xt)
= w'(s,a) + w'(a,b) + … + w'(x,t)
= [ w(s,a)+h(s)-h(a) ] + [ w(a,b)+h(a)-h(b) ] + … + [ w(x,t)+h(x)-h(t) ]
= w(s,a) + w(a,b) + … + w(x,t) + h(s) - h(t)
= w(sab…xt) + h(s) - h(t)
= w(s~t) + h(s) - h(t)

一加一减相消，得到简洁的结果。

由于 h(s) 和 h(t) 都是定值，由 s 点到 t 点的每一条路径，权重的变动量都一样，权重大小关係保持不变，于是乎由 s 点到 t 点的最短路径保持不变。图上的最短路径，不会因为调整权重而移动。

再看看环。图上的一只环 s~s，权重变成了：

  w'(s~s)
= w'(sab…s)
= w(sab…s) + h(s) - h(s)
= w(s~s)

环的权重保持不变。图上的负环，不会因为调整权重而移动。

重新调整权重为非负数

调整权重而不会影响最短路径、负环的方法已经有了。现在要想想如何好好设定 h(x) 的值，让每一条边的权重都调整为非负数。

最短路径找到后，图上每一条边都不可能再做 relaxation，式子可写成 d(i) + w(i, j) >= d(j)，经过移项之后就是 w(i, j) + d(i) - d(j) >= 0，正好就是调整权重的式子。因此，只要令 h(x) 是由一个起点到各个 x 点的最短路径长度，那麽调整后的权重就是非负数；无论起点是哪一点，这个式子都会成立。

至于起点该选在哪裡好呢？由于图上的每一条边都必须调整权重、图上每一个点都必须设定 h(x) 值，因此选定的起点必须能够到达图上每一个点，如此图上每一个点才有 h(x) 值。

巧妙的解决方式是：增加一个超级起点，连向图上每一个点，以确保选定的起点能够到达图上每一个点。

演算法

一、增加一个超级起点，连向原图每一个点，权重设定为零。
二、以超级起点作为起点，执行 Bellman-Ford Algorithm。
　甲、求得超级起点到原图每一个点的最短路径长度，作为 h(x)。
　乙、顺便检查原图是否有负环。
三、调整原图每一条边(i, j) 的权重：
　　w'(i, j) = w(i, j) + h(i) - h(j)
四、原图每一个点分别作为起点、分别执行 Dijkstra's Algorithm，
　　找出图上任两点之间的最短路径。
五、找出最短路径后，对照原图求出正确的最短路径长度。
　　或者直接利用 h(x) 逆推：w(s~t) = w'(s~t) - h(s) + h(t)。

时间複杂度

当图上的边很少时，做一次 Bellman-Ford Algorithm 以及做 V 次 Dijkstra's Algorithm，比做一次 Floyd-Warshall Algorithm 还快一点点。各位可以算一算时间複杂度。

延伸阅读：以最短路径长度重新调整权重

以最短路径长度重新调整权重的话，所有最短路径上的边，权重都会变成零。当要找出一张图所有的最短路径时，这是一个很好用的特性。

延伸阅读：重新调整权重为非负数，另一种方式

先前提到，令 h(x) 是由一个起点到各个 x 点的最短路径长度，根据最短路径之三角不等式 h(i) + w(i, j) >= h(j)，移项之后 w(i, j) + h(i) - h(j) >= 0，因此以 w'(i, j) = w(i, j) + h(i) - h(j) 得调整每一条边的权重为非负数。

事实上呢，令 h(x) 是由各个 x 点到一个终点的最短路径长度，根据最短路径之三角不等式 w(i, j) + h(j) >= h(i)，移项之后 w(i, j) - h(i) + h(j) >= 0，因此以 w'(i, j) = w(i, j) - h(i) + h(j) = w(i, j) + (-h(i)) - (-h(j)) 亦得调整每一条边的权重为非负数。

起点出发改为抵达终点，调整权重要记得变号。

Point-to-Point Shortest Path: A* Search

用途

一张有向图，选定一个起点与一个终点，找出起点到终点的最短路径。

套用 Single Source Shortest Paths

执行单源最短路径演算法，一旦遇到终点就马上停止，比起点到终点还要长的路径就能略过计算，提升效率。

然而引申一个问题：单源最短路径演算法找出了起点衍生的所有最短路径，既然现在已经知道终点，那麽没有通往终点的那些最短路径们，能不能略过计算呢？

套用 State Space Search

套用“ State Space Search ”的估计函数 h(x)。好的估计函数，容易直奔终点，改善了方才的问题。

二维平面上的最短路径，可以用“当前点到终点的直线距离”作为估计函数 h(x)。一般的图的最短路径，则无规律可循，无法估计距离。

时间複杂度

儘管 A*与 Label Setting Algorithm 的时间複杂度相同，但是 A*容易直奔终点，效率快上许多。现行的时间複杂度标记法无法明确描述 A*与 Label Setting Algorithm 的差异。

调整函数、估计函数

Johnson's Algorithm 的调整函数 h(x)，State Space Search 的估计函数 h(x)，两者都可以用来改变遍历顺序，并且不影响最短路径的位置。事实上两者大有关联。

套用原本权重 w(i, j) 的 Label Setting Algorithm、套用原本权重 g(x) 的 Uniform-cost Search，两者的遍历顺序完全相同。

  min { d(s~i) + w(i,j) }   寻找不在树上、离起点最近的点。
   j
= min { d(s~j) }            整理成 A*的模样
   j
= min { g(j) }              整理成 A*的模样
   j

套用调整函数 w(i, j) - h(i) + h(j) 的 Label Setting Algorithm、套用估计函数 g(x) + h(x) 的 A*，两者的遍历顺序也正巧相同！

  min { d'(s~i) + w'(i,j) }               寻找不在树上、
   j                                      离起点最近的点
= min { d(s~i) - h(s) + h(i)              分解成原本权重
      + w(i,j) - h(i) + h(j) }
= min { d(s~i) + w(i,j) + h(j) - h(s) }   整理
= min { d(s~j)          + h(j) - h(s) }   整理成 A*的模样
= min { g(j)            + h(j) - h(s) }   整理成 A*的模样
= min { g(j)            + h(j) } - h(s)   h(s) 为定值

h(s) 从头到尾都是固定值，所以不影响取最小值的结果。

因此，用 Label Setting Algorithm 得取代 A*，用 A*得取代 Label Setting Algorithm。

因此，调整函数得当作估计函数，估计函数得当作调整函数。调整权重之后，即是完成估计了。

注：以群论的观点来看，一种调整函数可以视作图上所有点的一种 permutation。以调整函数来描述 permutation，不知道有没有数学家作过研究。

调整函数调整权重为非负数，估计函数就满足三角不等式。

调整权重至非负数，可以使用抵达终点的最短路径长度；对应到估计函数，就是估计得最准确的方式，并且满足三角不等式，时间複杂度可降至多项式时间。【待补文字】

Landmark

调整权重至非负数，亦可以使用任意一点出发、抵达任意一点的最短路径长度（甚至是多点），而且都具有估计函数的效果！此点称作“地标”。

若需要多次计算点到点最短路径，可以预先设定一点或多点作为地标，预先计算地标出发、或者抵达地标的最短路径长度，并且预先调整权重，作为一个公用的估计函数。如此一来，每次计算点到点最短路径时，每次都能达到 A*的效果。

当地标设立在交通要衝、四通八达之处，遍历时就容易直奔要衝，节省时间！

若仅计算一次点到点最短路径，地标是没有用处的。因为处理地标，就是计算单源最短路径，不如直接求解。

Point-to-Point Shortest Path: ALT Algorithm

注记

Andrew V. Goldberg, Chris Harrelson. Computing the Shortest Path: A* Search Meets Graph Theory. ACM-SIAM Symposium on Discrete Algorithms, 2005.

ALT Algorithm 是作者自行取名。ALT 是指 A*、Landmark、Triangle Inequality 三样东西。

原论文只讨论每一条边皆为非负权重的图，事实上可以推广至一般的图。

合併调整函数

两个调整函数 h1(x) 与 h2(x) 能够调整权重为非负数，两者的最大值（最小值）亦能够调整权重为非负数、得作为调整函数。証明很简单，但是数学式子有点落落长，参考看看就好：

w(i, j) + h1(i) - h1(j) >= 0
w(i, j) + h2(i) - h2(j) >= 0

max { w(i, j) + h1(i) - h1(j), w(i, j) + h2(i) - h2(j) } >= 0
max { w(i, j), w(i, j) } + max { h1(i), h2(i) } - max { h1(j), h2(j) } >= 0
w(i, j) + max { h1(i), h2(i) } - max { h1(j), h2(j) } >= 0

取最大值的好处，以估计函数的立场来看，就是估计更加精准了，仍旧不高估。

地标出发、抵达地标的最短路径长度，合併成一个调整函数。

地标出发、抵达地标的最短路径长度，两者取最大值，合併成一个调整函数，遍历时更容易直奔终点。

也可以选定多个地标，求出地标出发、抵达地标的多源最短路径长度，两者取最大值，合併成一个调整函数。求多源最短路径，只要把所有起点（终点）的距离设定为零，再执行单源最短路径演算法即可；时间複杂度亦等同于单源最短路径演算法。

也可以选定多个地标，个别求出地标出发、抵达地标的单源最短路径长度，全部取最大值，合併成一个调整函数。如此能形成估计更加精准的调整函数，但是计算时间就会变长。

如何选择地标

目前还没有定论。地标均匀分布、地标两两相距最远、地标放在主干道上宛如收费站、地标呈辐射状散开，各位可以多加研究。如何找到交通要衝也是一个好问题。

如果图上有负边，为了方便起见，最好调整每一条边为非负数。请参考 Johnson's Algorithm，必须让图上每一个点都拥有最短路径长度；或者更精确的说，必须让图上每一条负边的端点都拥有最短路径长度。

演算法

一、Preprocessing：选定地标。
　　若有负边，必须让图上每一条负边的端点，都拥有最短路径长度，
　　以调整权重为非负数。
二、Preprocessing：制作调整函数。
　甲、计算地标出发、抵达地标的最短路径长度。
　　回、若为正权重图，则採 Label Setting Algorithm 系列。
　　回、若为负权重有向图，则採 Label Correcting Algorithm 系列。
　　回、若为负权重无向图，则採 T-Join。
　乙、取两者最大值，合併成一个调整函数。
三、计算点到点最短路径。
　　一边调整权重，一边遍历。

Point-to-Point Shortest Path: Matching

有向图演算法

请先具备“ Matching ”之知识。

利用最小权二分匹配，解决有向图的点到点最短路径问题。但是图上不得有负环。

一、额外建立二分图：
　点：X 侧、Y 侧都有 V 个点。
　边：若原图有一条 i 点到 j 点的有向边，
　　　则二分图就有一条 Xi 点到 Yj 点的边。
二、转化问题：
　口、增加 Xi 点到 Yi 点的边，权重设为零。
　口、X 侧，去掉起点，也去掉连至起点的边。
　口、Y 侧，去掉终点，去掉终点连出的边。
三、计算最小权二分匹配。

一、额外建立二分图：
　口、複制原图的 adjacency matrix。
二、转化问题：
　口、对角线改为零。
　口、去除起点编号的 column。
　口、去除终点编号的 row。
　　　（最后成为(V-1)*(V-1) 矩阵。）
三、计算最小权二分匹配。

无向图演算法

利用最小权匹配，解决无向图的点到点最短路径问题。但是图上不得有负环。

一、额外建立无向图：
　点：V 个原来的点，再加上 V 个複制的点。
　边：若原图有一条 i 点到 j 点的无向边，
　　　则新图就有：
　　　一条 i 点到 j 点的无向边、
　　　一条 i'点到 j 点的无向边、
　　　一条 i 点到 j'点的无向边、
　　　一条 i'点到 j'点的无向边。
二、转化问题：
　口、增加 i 点到 i'点的无向边，权重设为零。
　口、去掉起点，也去掉连著该点的边。
　口、去掉终点的複制点，也去掉连著该点的边。
三、计算最小权匹配。