12 第 k 短路径

给一个有向无负圈图，以及两个点 s 和 t、还有一个正整数 k。请找出所有不同的 s-t 走访(walk；允许重复经过点) 中总长前 k 短的走访。

12.1 从传统的 Dijkstra 演算法修改

我们可以利用动态规划加上 Dijkstra 的演算法，在每一个点记录下不只一个最短距离，使用一个优先权伫列(或堆积) 纪录下最小的 k 个距离数值。如此一来，当我们处理到第 k 个从 s-t 之间的距离时，就自然而然地找到这条路径啦！

由於每一个点会被拜访至多 k 次，因此这个变形的 Dijkstra 演算法时间复杂度是 O(k(m + n log (kn)))。

12.2 Eppstein 的演算法 part 1

Eppstein 在 1994 年提出了一个基於持久化堆积 (persistent heap) 的概念的演算法，时间复杂度来到了很猛的 O(m + n log n + kn)。我们今天不一定有机会说完整个演算法，但其中 Eppstein 队最短路径的重要观察可以说是相当值得一瞧。

1970 年代陆续有几篇论文(Yen’s Algorithm 这个我们之後会提到) 描述了第二短路径的性质：如果我们已知有一条 s-t 最短路径 P。那麽这第二短路径，必定可以是一条沿着 P 一直走到某个点，然後突然岔出去、而且岔出去以後，沿着该点到 t 的最短路径一路抵达终点。

Eppstein 首先做了一棵以 t 为汇根(sink node) 的最短路径树 T。接着，我们可以将图上所有的边 e (u→ v) 赋予一个新的权重 δ(e) := w(e) + dist(v, t) - dist(u, t)。这个权重 δ(e) 就代表了：岔出去以後会带给这条走歪掉的最短路径多少权重的加持。

这个概念相当有趣：我们可以仅仅用一条走岔的边 e，就代表了第二短路径。而且，我们可以用一个序列的走岔的边，来描绘任何一条 s-t 走访。如果我们能将这些走岔的边，依照新权重 δ(e) 建立最小堆积，那麽只要不断地将最小值取走就可以找到「只有一条走岔边」的第 k 短路径了。Eppstein 将这个想法延伸，建立另一个最小堆积，这时候不断将最小值取走，可以顺利找出「不只一条走岔边」的第 k 短路径！下次我们再来说说要如何利用这个特性，用更有效率的方法描述 k-短路径。

参考资料：

https://en.wikipedia.org/wiki/K_shortest_path_routing

挖，我居然能够连续生出 30 天的内容...满痛苦的哈哈，可惜没有太多时间顺过文章内容...
之後如果加上有证明的版本再放到这个已经停更好一阵子的 演算法的分析与证明 与大家分享~

这边应该还是会陆续更新，之前列出了一些主题，还没有一一介绍完。
如果有特别想知道什麽样的图论演算法也可以在下面留言跟我说唷，感谢大家~