Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks

Robert Geisberger, Peter Sanders, Dominik Schultes, and Daniel Delling. 2008. Contraction hierarchies: faster and simpler hierarchical routing in road networks. In Proceedings of the 7th international conference on Experimental algorithms (WEA'08), Catherine C. McGeoch (Ed.). Springer-Verlag, Berlin, Heidelberg, 319-333.

内容

  • 問題
    • road network の shortest path querying
  • アルゴリズム
    • そこまでの図 ＋ スライド 9 枚目の擬似コードわかりやすすぎ．超シンプル．
    • 前処理: 頂点を適当な順に並べ，順番に contract (「下」の頂点から「上」の頂点）
      • 頂点 v を contract = それを消す代わりに，近傍達の間に必要なら shortcut を加える
    • クエリ: 下の頂点から上の頂点へ方向のみのDijkstraを両側からやる．
  • 頂点を決める順番が大事っぽい．
  • 実験結果
    • 前処理そこそこ
    • クエリは <1ms
      • Hub-Labeling はマジで <1us なのでソレと比べるとクエリはだいぶ遅い（仕方ないね）
      • でも前処理は Hub-Labeling より早い

感想

Hub-Labegling 読もうとしたけど CH 出てきまくってたのでこっちに目を通すことにした．

スライドだけ見た．演習 3 のネタ探しのつもり． simple らしいので実装＆実験できる？

終わったら Hub-Labeling 読んで貰って余裕あったらそっちもやってもらうとか

あと文字列系のネタも用意したいなぁ，なんかあるかなぁ