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 天的內容...滿痛苦的哈哈，可惜沒有太多時間順過文章內容...
之後如果加上有證明的版本再放到這個已經停更好一陣子的 演算法的分析與證明 與大家分享~

這邊應該還是會陸續更新，之前列出了一些主題，還沒有一一介紹完。
如果有特別想知道什麼樣的圖論演算法也可以在下面留言跟我說唷，感謝大家~