iT邦幫忙

2021 iThome 鐵人賽

DAY 30
0
Software Development

圖論與演算法之間的相互應用系列 第 30

第 k 短路徑問題 (1)

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

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


上一篇
近似最短路徑 (9)
系列文
圖論與演算法之間的相互應用30

尚未有邦友留言

立即登入留言