Eppstein's Algorithm (Find the K shortest paths) 解説と実装 (Python)

Qiitaに記事を投稿しました。

K Shortest Path Problem (KSP) とは, K番目(ある文脈では1~K番目)に短いパスを見つける問題です。多重有向グラフについて始点と終点を固定した上でK shortest path problelmを解く方法として Eppsteinのアルゴリズムを実装しました[1]。

キーポイントについては, 以下のブログに簡潔にまとめられているため, こちらを参考にしてください。 Finding the k Shortest Paths (SICOMP'98) [2]

計算量についてまとめると, グラフ $G$ のノード数を $n$ , エッジ数を $m$ とすると,
Path Graph $P$ の作成に $O(m+n\log n)$
それを用いて第1~K最短路を導出するのに $O(K)$ , すなわち全体で $O(m+n\log n + K)$ となります。
Yenのアルゴリム[3] では $O(Kn(m+n\log n))$ なので, これと比較すると大幅に計算長が削減されていることが分かります。