最短経路問題

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

2頂点対最短経路問題

特定の2つのノード間の最短経路問題。一般的に単一始点最短経路問題のアルゴリズムを使用する。

単一始点最短経路問題 (SSSP：Single Source Shortest Path)

特定の1つのノードから他の全ノードとの間の最短経路問題。この問題を解くアルゴリズムとしては、ダイクストラ法やベルマン-フォード法がよく知られている。

全点対最短経路問題 (APSP : All Pair Shortest Path)

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

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

アルゴリズム	計算量	作者
幅優先探索	${\displaystyle O(E)}$

アルゴリズム	計算量	作者
	${\displaystyle O(V^{2}EL)}$	Ford 1956
ベルマン-フォード法	${\displaystyle O(VE)}$	Bellman 1958, Moore 1959
	${\displaystyle O(V^{2}\log {V})}$	Dantzig 1958, Dantzig 1960, Minty (cf. Pollack & Wiebenson 1960), Whiting & Hillier 1960
ダイクストラ法（リスト）	${\displaystyle O(V^{2})}$	Leyzorek et al. 1957, Dijkstra 1959
ダイクストラ法（修正二分ヒープ）	${\displaystyle O((E+V)\log {V})}$
. . .	. . .	. . .
ダイクストラ法（フィボナッチヒープ）	${\displaystyle O(E+V\log {V})}$	Fredman & Tarjan 1984, Fredman & Tarjan 1987
	${\displaystyle O(E\log {\log {L}})}$	Johnson 1982, Karlsson & Poblete 1983
Gabow 法	${\displaystyle O(E\log {\frac {E}{V}}L)}$	Gabow 1983b, Gabow 1985b
	${\displaystyle O(E+V{\sqrt {\log {L}}})}$	Ahuja et al. 1990

アルゴリズム	計算量	作者
ベルマン-フォード法	${\displaystyle O(VE)}$	Bellman 1958, Moore 1959

最短経路の距離は部分構造最適性が成立しており、下記漸化式が成立する。証明は『アルゴリズムイントロダクション』（ISBN 978-4764904088）などを参照。

${\displaystyle V}$ が頂点、${\displaystyle E}$ が辺、${\displaystyle c(s,v)}$ が辺の重み、${\displaystyle \mathrm {dist} (s,v)}$ が最短経路の距離。${\displaystyle s,v,w\in V}$。${\displaystyle w\neq s}$。

${\displaystyle \mathrm {dist} (s,s)=0}$ とおく。

${\displaystyle \mathrm {dist} (s,w)=\min\{\mathrm {dist} (s,v)+c(v,w)\mid (v,w)\in E\}}$ が成立する。

単一始点の場合 ${\displaystyle c(s,v)=1}$ なら幅優先探索が、${\displaystyle c(s,v)\geq 0}$ ならダイクストラ法が、そうでないならベルマン-フォード法が使える。

辺の重みが非負値の2頂点対最短経路問題で、最短経路の距離の下限値が分かっている場合はA*を使うと、ダイクストラ法よりも速く求まる。

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

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

• 巡回セールスマン問題 - グラフ内の全頂点を通り、始点に帰ってくる最短閉路を求める問題。NP困難であることが知られている。
• 中国人郵便配達問題 - グラフ内の全ての辺を1回以上通り、始点に帰ってくる最短閉路を求める問題。

表 話 編 歴 数理最適化 • 最適化問題 : メソッド • ヒューリスティック
非線形（無制約）	… 関数　 黄金分割探索 直線探索 ネルダー–ミード法 放物線補間 パウエル法 勾配法 収束性 信頼領域 ウルフ条件 準ニュートン法 BFGS法 ブロイデン法 L-BFGS法 DFP法 SR1法 BHHH法 その他の求解法 ガウス・ニュートン法 最急降下法（確率的） レーベンバーグ・マーカート法 共役勾配法（非線形共役勾配法） 打ち切りニュートン法 ドッグレッグ法 鏡像 座標 バルジライ・ボールウェイン法 … ヘッセ行列 最適化におけるニュートン法
非線形（制約付き）	一般 バリア関数 ペナルティ関数法 微分可能 ラグランジュの未定乗数法 拡張ラグランジュ関数法 逐次二次計画法 逐次線形計画法 逐次線形二次計画法
凸最適化	凸最小化 切除平面法 簡約勾配法 劣勾配法 近接勾配法 線形 および 二次 内点法 アフィンスケーリング法 カーマーカーの射影変換法 メロートラの予測子修正子法 基底-交換 単体法 改訂単体法 十文字法 レムケの相補掃き出し法 その他 カチヤンの楕円体法 有効制約法 列生成法 ベンダーズ分解法
組合せ最適化	系列範例 (Paradigms) 近似アルゴリズム 動的計画法 貪欲法 整数計画問題（分枝限定法・分枝カット法・分枝価格法） グラフ理論 最小全域木 ブルーフカ法 クラスカル法 プリム法 最短経路問題 ベルマン–フォード法 ダイクストラ法 ワーシャル–フロイド法 ジョンソン法 ネットワークフロー (最大流問題) ディニッツ法 エドモンズ・カープ法 フォード・ファルカーソン法 プリフロープッシュ法
メタヒューリスティクス	進化的アルゴリズム（進化戦略・遺伝的アルゴリズム） 山登り法 局所探索法 焼きなまし法 タブーサーチ 群知能 ベイスンホッピング法 量子焼きなまし法
カテゴリ（最適化 • アルゴリズム） • ソフトウェア