Question

名词解释

走道（Walk）：一连串的边。可以重複经过同样的点和边，可以来来回回绕圈子。

迹（Trail）：一条走道，没有重複经过同样的边。

路径（Path）：一条走道，没有重複经过同样的点（与边）。

封闭走道（Closed Walk）：头尾衔接的走道。

迴路（Circuit）：头尾衔接的迹。Closed Trail。

环（Cycle）：头尾衔接的路径。Closed Path。

自环（Loop）：自己连向自己的边。长度为 1 的环。

Shortest Walk 与 Shortest Path

无向图。如果有负边，“最短走道”将来回走负边，长度成为负无限大。如果没有负边，“最短走道”等于“最短路径”。

有向图。如果有负环，“最短走道”将不断绕负环，长度成为负无限大。如果没有负环，“最短走道”等于“最短路径”。

无向图没负边、有向图没负环的情况下，一条走道重複经过同一条边、同一个点，一定让走道变长。此时“最短走道”决不会重複经过同样的点和边，即是“最短路径”。

Shortest Walk 的演算法

先前介绍的演算法，其实全部都是“最短走道”的演算法！诸如 Dijkstra's Algorithm、Bellman-Ford Algorithm、Floyd-Warshall Algorithm 等等都是！而且不需要区分无向图、有向图，也不需要预设图上无负环，都能得到正确答案。

最短走道
　　　　无负边　　　　有负边、没负环　有负环（想当然有负边）
有向图　先前的演算法　先前的演算法　　先前的演算法
　　　　　　　　　　　　　　　　　　　答案是负无限大
无向图　先前的演算法　先前的演算法　　先前的演算法
　　　　　　　　　　　答案是负无限大　答案是负无限大

最短路径
　　　　无负边　　　　有负边、没负环　有负环（想当然有负边）
有向图　先前的演算法　先前的演算法　　没有好方法，NP-complete
无向图　先前的演算法　T-Join　　　　　没有好方法，NP-complete

目前世界上的所有教科书，把这些“最短走道”的演算法，硬是拿去计算“最短路径”。然后“最短走道”人间蒸发。

这种现象源自历史因素──古时候大家没把 path 和 walk 分得很清楚，walk 常常被叫做 path。

k Shortest Path

k Shortest Walk

给定起点与终点，排名第 k 短的走道。有可能跟最短走道一样长。或许可以翻译为“第 k 短走道”。

可以直接套用先前所学的 Dijkstra's Algorithm，把 DP 表格开大一点，每个点都储存前 k 短的长度，就能解决问题。时间複杂度为 O(K * (E+VlogV))。

UVa 10740

k Shortest Path 与 k Shortest Trail

“第 k 短路径”、“第 k 短迹”尚无有效率的演算法，大多是使用穷举法，穷举所有可能的路径。时间複杂度本是指数时间，但如果配合了 heuristic function，理想状态之下，时间複杂度得宣称是多项式时间。

主要的演算法有 Yen's Algorithm 与 MPS Algorithm 两个。

http://imlazy.ycool.com/post.1956603.html

http://code.google.com/p/k-shortest-paths/

http://www.mat.uc.pt/~eqvm/OPP/KSPP/KSPP.html

http://blog.csdn.net/sharpdew/archive/2005/08/05/446510.aspx

ICPC 3624

Next-to-Shortest Path

Strictly Second Shortest Walk

给定起点与终点，“严格次短走道”是权重不等于最短走道、权重尽量小的走道。可能有许多条。

有向图有负环、无向图有负边，答案是负无限大，没有讨论意义。以下讨论有向图无负环、无向图无负边，此时最短走道恰是最短路径。

不想走这条路，就必须改走别条路。不想走最短走道（最短路径），而想走严格次短走道，那就先列出所有的最短走道（最短路径），再寻找别条路。

一张图，给定起点与终点，所有的最短路径形成了“最短路径图”。图上只有正边时，最短路径图是有向无环图 DAG；图上只有零边负边、没有负环时，最短路径图可能会额外出现零环。

有向图上，严格次短走道一定经过“最短路径图”以外的边。

无向图上，严格次短走道还可以逆行“最短路径图”上面的边。

无论有向图还是无向图，将严格次短走道定义成有向边，比较方便。

替代路线太长，于是观察其中一条边，此处暂称为替代边。严格次短走道越短越好。当有一条走道经过替代边 xy，要使此走道尽量短，唯一的方法就是：从起点 s 到 x 必须是最短路径，从 y 到终点 t 也必须是最短路径。最后只要使用穷举法，穷举所有可能的替代边，即可找到其中一条严格次短走道。

一、预先计算起点 s 出发的单源最短路径。
二、预先计算抵达终点 t 的单源最短路径。
三、穷举图上每一条边 xy 作为替代边（无向图则视作双向都有边）：
　甲、取得最短路径 s⤳x。
　乙、取得最短路径 y⤳t。
　丙、串成一条走道 s⤳x→y⤳t。
　　回、若 s⤳x→y⤳t 是最短路径，表示边 xy 不是替代边，捨弃之。
　　　　因为最短路径有许多条，所以取其长度，再用长度做判断。
　　回、若 s⤳x→y⤳t 不是最短路径，就有可能是严格次短走道，记录之。
　　　　当中最短者，便是严格次短走道。

时间複杂度等同于单源最短路径。

UVa 10342

Strictly Second Shortest Path（Next-to-Shortest Path）

给定起点与终点，“严格次短路径”是权重不等于最短路径、权重尽量小的路径。

当图上只有正边，时间複杂度等同于单源最短路径。仿效前面段落，将严格次短路径分为两种情况“经过最短路径图的边与以外的边”与“经过最短路径图的边与反方向边”。

s⤳x→y⤳t 必须是路径、而非走道。在最短路径图上，寻找从 s 往 x 跨 y 的替代路径入口 x'，寻找从 y 往 t 跨 x 的替代路径出口 y'，同时确保替代路径不相交，最后改成计算路径 s⤳x'→y'⤳t。我没能弄懂细节，请读者自行研究原始论文。

有向图的替代路径，请参考本站文件“ Dominator ”。

Replacement Path

Replacement Path

道路崩塌、道路阻塞，如何找到最短的替代道路呢？

一张图，给定起点与终点。切断图上一条边之后，新的最短路径，称作此边的“替代路径”，可能不存在（长度无限大）、可能有许多条。

替代路径
　　　　无负边　　　　有负边、没负环　有负环（想当然有负边）
有向图　先前的演算法　先前的演算法　　没有好方法，NP-complete
无向图　先前的演算法　没有人研究？　　没有好方法，NP-complete

观察最短路径图。删除桥，才会改变最短路径长度。

当图上只有正边零边，桥的两侧仍是单源最短路径图。替代路径是另一座横跨两侧的桥。穷举所有横跨两侧的桥，就能找到最短的替代路径。

当图上有负边，终点侧不见得是单源最短路径图。目前尚未出现特殊演算法，只能删除桥之后，以新图找最短路径。

Shortest Path 的衔接与断开

一、a⤳b、b⤳c 是最短路径，那麽 a⤳b⤳c 是不是最短路径？

不一定。此即 relaxation 的用途。

二、a⤳b⤳c 是最短路径，那麽 a⤳b、b⤳c 是不是最短路径？

a⤳b 一定是，b⤳c 不一定：图上只有正边零边则是，有负边则不一定。例如边 ab 或者路径 a⬿b 为负值，那麽从 b 到 c 的最短路径可能是 b⤳a⤳c，往回走负边、负路，争取更短的长度。

演算法（Malik-Mittal-Gupta Algorithm）

适用于图上只有正边零边、没有负边。用来找到图上每一条边的其中一条替代路径。不过我们通常只关心最短路径图上的桥。

两棵最短路径树，起点侧逐步延展、终点侧逐步削减。随时记录当下所有桥，随时求得次佳的桥。所有桥放入 Priority Queue，加快速度。

时间複杂度为 O(ElogE)。可以改写成 O(ElogV)。

Graph Geodesic

Eccentricity

eccentricity(i) = max d(i, j)
                  j∊V

d(i, j) 为 i 点到 j 点的最短路径

在一张无向图上面，给定图上一点，以最短路径长度当作距离，找出离此点最远的一点，这两点之间的距离就叫做“偏心距”。

Diameter / Radius

diameter(G) = max eccentricity(i) = max d(i, j)
              i∊V                  i,j∊V

radius(G)   = min eccentricity(i)
              i∊V

一张无向图的“直径”是图上所有偏心距当中最大的一个，一张无向图的“半径”是图上所有偏心距当中最小的一个。“直径”也可以直接想做是，一张图上长度最长的一条最短路径之长度。

【注：有时候为了方便，直径和半径会定义成一段路径，而不是一个数值。】

一张图可能会有许多条直径、许多条半径。

直径和半径都是最短路径。根据最短路径的性质，直径和半径中间截一段路径下来，也都会是最短路径。

要计算一张无向图的直径与半径是很简单的，首先算好所有两点之间最短路径，然后按照定义来算就可以了。