iwiwi 備忘録

学んだことを殴り書きます。自分向けのメモです。

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) でもできるらしい.