Finding the k Shortest Paths (SICOMP'98)
- s, t が与えられるので,k 本の最短路を計算する
- O(m + n log n + k) でできるよっていう論文
キーとなるアイディア
- t からの逆最短路木を T とする
- 例によって,ポテンシャルを使って辺の重みを変換する.T に含まれる辺の重みは 0 になる.
- パス p は,T に含まれない辺だけの sidetracks(p) と一対一対応する
- sidetracks(p) で考えると,最後の要素を削ったやつを親だと思うと,パスたちは木,しかも親のほうがコストが小さいヒープを構成する
- このヒープで top-k を取れば,k 本の最短路に相当する
- しかし,このヒープは次数が定数とは限らないので,その部分の計算量が保証できない……!
Eppstein のアルゴリズム
そこを打開するために,グラフから頑張って定数次数の無限ヒープ(ループがあるだけ)を構成する.
- グラフ H(G)
- 各頂点で,そこから使える sidetrack 辺の heap を作る
- 永続にして,T の親とマージしている感じにすると全体で O(n log n) で作れる
- 全体で見ると,頂点に重み,辺には重み無しの有向グラフ.しかも出次数≦3 (つまり 3-heap)
- グラフ P(G)
- 頂点の重みを,辺への重みに変換する
- その上で,sidetrack 辺を使った時にどこへ行くかっていう辺をたす
- 出次数≦4 (つまり 4-heap)
あとはこのヒープで top-k をとるだけ.最良優先探索をすれば O(k log k).Frederickson のアルゴリズムというものがあって O(k) でもできるらしい.