大規模最短路問題に対するダイクストラ法の高速化

安井雄一郎、藤澤克樹、笹島啓史 （中央大学）, 後藤和茂（マイクロソフト）. 大規模最短路問題に対するダイクストラ法の高速化. 日本オペレーションズ・リサーチ学会和文論文誌．

• Dijkstra を高速に実装するためにはどうすればよいかという論文．
• キューはどうしたほうが良いか？
  • 2 分ヒープ？ 1-level bucket? multi-level bucket?
  • k-ary heap を特に取り扱っている
  • あとヒープの処理をちょっと改善
  • 個人的には，quick heap みたいな他の高速と言われるヒープを使った時の速度はどうなるのか，というのが疑問
• グラフ等の情報をキャッシュ乗りやすくするにはどうすればよいか？
• 実験が凄い精密に行われていて，色々検証され，ボトルネックが解明されている