最短経路問題

出典: フリー百科事典『ウィキペディア（Wikipedia）』

グラフ理論における最短経路問題（さいたんけいろもんだい）とは、与えられた重み付きグラフの2つのノード間を結ぶエッジの中で、最小の重みを持つ経路を求める問題である。

特定の2つのノード間の最短経路問題を2頂点対最短経路問題と呼ぶ。

特定の1つのノードから他の全ノードとの間の最短経路問題を単一始点最短経路問題と呼ぶ。この問題を解くアルゴリズムとしては、ダイクストラ法がよく知られている。

グラフ内のあらゆる2ノードの組み合わせについての最短経路問題を全点対最短経路問題と呼ぶ。この問題を解くアルゴリズムとしては、ワーシャル-フロイド法が知られている。

このような分類がされているのは、後者の問題が単に前者の問題を初期条件（ノード）を変えて繰り返し解くのではなく、アルゴリズムの過程で得た情報を利用して計算量を減らすことが可能となるからでもある。

最短経路問題の身近な応用例には、鉄道の経路案内（駅すぱあと、駅探、NAVITIMEなど）がある。駅をノードとし、駅と駅の所要時間を重みとしたエッジとして、鉄道線路をグラフ化して最短経路を求めている。

類似の問題として、グラフ内の全ノードを通る最短経路を求める巡回セールスマン問題があるが、こちらはNP困難であることが知られている。