最短経路問題

グラフ理論における最短経路問題（さいたんけいろもんだい、テンプレート:Lang-en-short）とは、重み付きグラフの与えられた2つのノード間を結ぶ経路の中で、重みが最小の経路を求める最適化問題である。

種類

2頂点対最短経路問題: 特定の2つのノード間の最短経路問題。一般的に単一始点最短経路問題のアルゴリズムを使用する。
単一始点最短経路問題（SSSP）: 特定の1つのノードから他の全ノードとの間の最短経路問題。この問題を解くアルゴリズムとしては、ダイクストラ法やベルマン-フォード法がよく知られている。
全点対最短経路問題: グラフ内のあらゆる2ノードの組み合わせについての最短経路問題。この問題を解くアルゴリズムとしては、ワーシャル-フロイド法が知られている。

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

アルゴリズム	計算量	作者
幅優先探索	<math>O(E)</math>

アルゴリズム	計算量	作者
	<math>O(V^2 EL)</math>	テンプレート:Harvnb
ベルマン-フォード法	<math>O(VE)</math>	テンプレート:Harvnb, テンプレート:Harvnb
	<math>O(V^2 \log{V})</math>	テンプレート:Harvnb, テンプレート:Harvnb, Minty (cf. テンプレート:Harvnb), テンプレート:Harvnb
ダイクストラ法（リスト）	<math>O(V^2)</math>	テンプレート:Harvnb, テンプレート:Harvnb
ダイクストラ法（修正二分ヒープ）	<math>O((E+V) \log{V})</math>
. . .	. . .	. . .
ダイクストラ法（フィボナッチヒープ）	<math>O(E+V \log{V})</math>	テンプレート:Harvnb, テンプレート:Harvnb
	<math>O(E \log{\log{L}})</math>	テンプレート:Harvnb, テンプレート:Harvnb
Gabow 法	<math>O(E \log{\frac{E}{V}} L)</math>	テンプレート:Harvnb, テンプレート:Harvnb
	<math>O(E+V \sqrt{\log{L}})</math>	テンプレート:Harvnb

アルゴリズム	計算量	作者
ベルマン-フォード法	<math>O(VE)</math>	テンプレート:Harvnb, テンプレート:Harvnb

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

最短経路とは逆の問題で、最長単純道問題もあるが、最短経路の場合は、最短経路の部分問題もやはり最短経路であるが、最長単純道の場合、部分構造最適性が成立していなく、貪欲法などで解くことが出来なく、辺の重みなしであっても、NP完全問題である。