はじめに NAVITIME JAPAN Advent Calendar 2019の19日目を担当いたします、経路探索アルゴリズムの研究開発をしているsuekiです。好きなデータ構造はセグメント木です。 本稿では弊社で導入している経路探索アルゴリズムの高速化手法とその課題について紹介します。 経路探索の高速化手法について グラフ上における2点間の経路探索と言えばダイクストラ法1が有名で、 弊社のサービスでも徒歩・自転車・車の経路はダイクストラ法をベースとしたアルゴリズムによって求められています。 ナイーブなダイクストラ法の計算量は $O((E+V)\log{V})$ 程度です。 しかし日本全国では数千万本のリンクが存在するため、より高速に経路探索を行うアルゴリズムが必要です。 クエリが来る前の事前処理の有無 事前処理と探索時間のバランス 多様なコストモデルの考慮可否 などに応じた様々な手法が