Question

路漫漫其修远兮，吾将上下而求索。《屈原．离骚》

“图”与“道路地图”

把一张图想像成道路地图，把图上的点想像成地点，把图上的边想像成道路，把权重想像成道路的长度。若两点之间以边相连，表示两个地点之间有一条道路，道路的长度是边的权重。

有时候为了应付特殊情况，边的权重可以是零或者负数，也不必真正照著图上各点的地理位置来计算权重。别忘记“图”是用来记录关联的东西，并不是真正的地图。

Path

在图上任取两点，分别作为起点和终点，我们可以规划许多条由起点到终点的路线。不会来来回回绕圈子、不会重覆经过同一个点和同一条边的路线，就是一条“路径”。

如果起点到终点是不通的，那麽就不存在起点到终点的路径。如果起点和终点一样，那麽就存在路径，路径是一个点、零条边。

路径也有权重。路径经过的每一条边，沿路加总权重，就是路径的权重（通常只加总边的权重，而不考虑点的权重）。路径的权重，可以想像成路径的总长度。

Shortest Path

Shortest Path

“最短路径”是由起点到终点、权重最小的路径，可能有许多条，也可能不存在。起点到终点不通、不存在路径的时候，就没有最短路径。

“最短路径”不见得是边最少、点最少的路径。

最短路径是 NP-complete 问题；当图上确定没有负环，才是 P 问题。“负环 Negative Cycle”是权重为负值的环。

Longest Path

最长路径和最短路径很类似。最长路径问题当中，每一条边的权重添上负号，就变成最短路径问题。反过来也是。

最长路径是 NP-complete 问题；当图上确定没有正环，才是 P 问题。

Shortest Path Tree

最短路径有一个特别的性质：每一条最短路径，都是由其它的最短路径延展而得。一条最短路径，截去末端之后，还是最短路径。

提到延展，就联想到树！引入延展的概念，最短路径们得以形成一棵树。

在图上选定一个起点，由起点到图上各点的最短路径们，形成一棵有向树，称作“最短路径树”。由于两点之间的最短路径不见得只有一条，所以最短路径树也不见得只有一种。

Shortest Path Graph【尚无正式名称】

在图上选定一个起点和一个终点，由起点到终点的所有最短路径们，形成一张有向图，称作“最短路径图”，只有唯一一种。

当图上每一条边的权重都是正数，最短路径图是有向无环图（Directed Acyclic Graph, DAG）。

两点之间有多条边

当一张图的两点之间有多条边，可以留下一条权重最小的边。这麽做不影响最短路径。

当图的资料结构为 adjacency matrix，任两点之间只能拥有一个权重值。此时权重值必须设定成权重最小的边的权重。

两点之间没有边（两点不相邻）

当一张图的两点之间没有边，可以补上一条权重无限大的边。这麽做不影响最短路径。

当图的资料结构为 adjacency matrix，任两点之间一定要有一个权重值。此时权重值必须设定成一个超大数字，当作无限大；不可设定为零，以免计算错误。

最短路径长度无限大、负无限大

当起点无法到达终点，就没有最短路径了。这种情况常被解读成：起点永远走不到终点，导致最短路径长度无限大。

最短路径的长度不可能是负无限大。最短路径的点和边不能重複，无法藉由负边、负环让长度不断减少。

Relaxation

最后介绍最短路径演算法一个共通的重要概念“鬆弛”。

寻找两点之间的最短路径时，最直观的方式莫过于：先找一条路径，然后再找其他路径，看看会不会更短，并记住最短的一条。

找更短的路径并不困难。我们可以寻觅捷径，以缩短路径；也可以另闢蹊径，取代原本的路径。如此找下去，必会找到最短路径。

寻觅捷径、另闢蹊径的过程，可以以数学方式来描述：现在要找寻起点为 s、终点为 t 的最短路径，而且现在已经有一条由 s 到 t 的路径，这条路径上会依序经过 a 及 b 这两点（可以是起点和终点）。我们可以找到一条新的捷径，起点是 a、终点是 b 的捷径，以这条捷径取代原本由 a 到 b 的这一小段路径，让路径变短。

找到捷径以缩短原本路径，便是 relaxation。

附录

最短路径演算法的功能类型：

Point-to-Point Shortest Path，点到点最短路径：
给定起点、终点，求出起点到终点的最短路径。一对一。

Single Source Shortest Paths，单源最短路径：
给定起点，求出起点到图上每一点的最短路径。一对全。

All Pairs Shortest Paths，全点对最短路径：
求出图上所有两点之间的最短路径。全对全。

有向图、最短路径演算法的原理：

Label Setting：
逐步设定每个点的最短路径长度，一旦设定后就不再更改。
负边不适用。

Label Correcting：
设定某个点的最短路径长度之后，之后仍可继续修正，越修越美。
整个过程就是不断重新标记每个点的最短路径长度。
负边适用。

Single Source Shortest Paths: Label Setting Algorithm

用途

一张有向图，选定一个起点，找出起点到图上各点的最短路径，即是找出其中一棵最短路径树。但是限制是：图上每一条边的权重皆非负数。

想法

当图上每一条边的权重皆非负数时，可以发现：每一条最短路径，都是边数更少、权重更小（也可能相同）的最短路径的延伸。

于是乎，建立最短路径树，可以从边数最少、权重最小的最短路径开始建立，然后逐步延伸拓展。换句话说，就是从距离起点最近的点和边开始找起，然后逐步延伸拓展。先找到的点和边，保证会是最短路径树上的点和边。

也可以想成是，从目前形成的最短路径树之外，屡次找一个离起点最近的点，（连带著边）加入到最短路径树之中，直到图上所有点都被加入为止。

整个演算法的过程，可看作是两个集合此消彼长。不在树上、离根最近的点，移之。

运用已知的最短路径，求出其他的最短路径。循序渐进、保证最佳，这是 Greedy Method 的概念。

演算法

一、将起点加入到最短路径树。此时最短路径树只有起点。
二、重複下面这件事 V-1 次，将剩馀所有点加入到最短路径树。
　甲、寻找一个目前不在最短路径树上而且离起点最近的点 b。
　乙、将 b 点加入到最短路径树。

运用 Memoization，建立表格记录最短路径长度，便容易求得不在树上、离根最近的点。时间複杂度是 O(V^3)。

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

一、将起点加入到最短路径树。此时最短路径树只有起点。
二、重複下面这件事 V-1 次，将剩馀所有点加入到最短路径树。
　甲、寻找一个目前不在最短路径树上而且离起点最近的点：
　　　以穷举方式，
　　　找一个已在最短路径树上的点 a，以及一个不在最短路径树上的点 b，
　　　让 d[a]+w[a][b]最小。
　乙、将 b 点的最短路径长度存入到 d[b]之中。
　丙、将 b 点（连同边 ab）加入到最短路径树。

实作

Single Source Shortest Paths: Dijkstra's Algorithm

想法

找不在树上、离根最近的点，先前的方式是：穷举树上 a 点及非树上 b 点，找出最小的 d[a]+w[a][b]。整个过程重覆穷举了许多边。

表格改为储存 d[a]+w[a][b]，就不必重覆穷举边了。每当一个 a 点加入最短路径树，就将 d[a]+w[a][b]存入 d[b]。找不在树上、离根最近的点，就直接穷举 d[]表格，找出最小的 d[b]。

演算法

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

一、重複下面这件事 V 次，以将所有点加入到最短路径树。
　甲、寻找一个目前不在最短路径树上而且离起点最近的点：
　　　直接搜寻 d[]阵列裡头的数值，来判断离起点最近的点。
　乙、将此点加入到最短路径树之中。
　丙、令刚刚加入的点为 a 点，
　　　以穷举方式，找一个不在最短路径树上、且与 a 点相邻的点 b，
　　　把 d[a]+w[a][b]存入到 d[b]当中。
　　　因为要找最短路径，所以儘可能记录越小的 d[a]+w[a][b]。
　　　（即是边 ab 进行 relaxation）

以 relaxation 的角度来看，此演算法不断以边 ab 作为捷径，让起点到 b 点的路径长度缩短为 d[a]+w[a][b]。

时间複杂度

分为两个部分讨论：

甲、加入点、穷举边：每个点只加入一次，每条边只穷举一次，刚好等同于一次 Graph Traversal 的时间。

乙、寻找下一个点：从大小为 V 的阵列当中寻找最小值，为 O(V)；总共寻找了 V 次，为 O(V^2)。

甲乙相加就是整体的时间複杂度。图的资料结构为 adjacency matrix 的话，便是 O(V^2)；图的资料结构为 adjacency lists 的话，还是 O(V^2)。

实作

Single Source Shortest Paths: Label Setting Algorithm + Priority Queue

演算法

找不在树上、离根最近的点，先前的方式是：穷举树上 a 点及非树上 b 点，也就是穷举从树上到非树上的边 ab，以找出最小的 d[a]+w[a][b]。

现在把 d[a]+w[a][b]的值通通倒进 Priority Queue。找不在树上、离根最近的点，就从 Priority Queue 取出边（与点）；每次 relaxation 就将边（与点）塞入 Priority Queue。

学过 State Space Search 的读者，可以发现此演算法正是 Uniform-cost Search，因此也有人说此演算法是考虑权重的 BFS。

Single Source Shortest Paths: Dijkstra's Algorithm + Priority Queue

演算法

时间複杂度与上一篇文章相同，然而效率较佳。

令 w[a][b]是 a 点到 b 点的距离（即是边的权重）。
令 d[a]是起点到 a 点的最短路径长度，起点设为零，其他点都是空的。
令 PQ 是一个存放点的 Priority Queue，由小到大排序键值。

一、把起点放入 PQ。
二、重複下面这件事，直到最短路径树完成为止：
　甲、尝试从 PQ 中取出一点 a，点 a 必须是目前不在最短路径树上的点。
　乙、将 a 点（连同其边）加入最短路径树。
　丙、将所有与 a 点相邻且不在树上的点的点 b（连同边 ab）放入 PQ，
　　　设定键值为 d[a] + w[a][b]，键值同时也存入 d[b]，
　　　但是会先检查 d[a] + w[a][b]是不是小于 d[b]，
　　　小于才放入 PQ，键值才存入 d[b]。
　　　（此步骤即是以边 ab 进行 ralaxation。）

Single Source Shortest Paths: Dial's Algorithm

演算法

用 Bucket Sort 代替表格，把 d[a]+w[a][b]的值通通拿去做 Bucket Sort。用在每条边的权重都是非负整数的图。

Single Source Shortest Paths: Gabow's Algorithm

用途

一张有向图，选定一个起点，找出起点到图上各点的最短路径，即是找出其中一棵最短路径树。但是限制是：图上每一条边的权重皆非负整数。

演算法

採用 Scaling Method。详细内容可参考 CLRS 习题 24-4，此处仅略述。

重複以下步骤 O(logC) 次，每个步骤要求出当下的最短路径：
一、令权重更加精细。
二、以上一步骤算得的最短路径长度来调整权重。
　　并以调整后的权重求最短路径，可用 O(V+E) 时间求得。
　　（调整过的权重刚好皆为非负数，且最短路径长度都不会超过 E。）
三、还原成正确的最短路径长度。

Scaling Method 的精髓，在于每次增加精细度后，必须有效率的修正前次与今次的误差。此演算法巧妙运用调整权重的技术，确切找出前次与今次差异之处，而得以用 O(E) 时间修正误差。

上述 O(V+E) 求最短路径的演算法，仍是运用 Dijkstra's Algorithm“最近的点先找”概念，只是求法有点小改变。首先开个 E+1 条 list，离起点距离为 x 的点，就放在第 x 条。只要依序扫描一遍所有的 list，就可以求出最短路径了。