最短経路問題

グラフ理論における最短経路問題（さいたんけいろもんだい、英: 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回以上通り、始点に帰ってくる最短閉路を求める問題。

参考文献

• Ahuja, Ravindra K.; Mehlhorn, Kurt; Orlin, James; Tarjan, Robert E. (April 1990). “Faster algorithms for the shortest path problem”. Journal of the ACM (ACM) 37 (2): 213–223. doi:10.1145/77600.77615. hdl:1721.1/47994. http://www.dtic.mil/cgi-bin/GetTRDoc?AD=ADA194031.
• Bellman, Richard (1958). “On a routing problem”. Quarterly of Applied Mathematics 16: 87–90. doi:10.1090/qam/102435. MR0102435.
• Dantzig, G. B. (January 1960). “On the Shortest Route through a Network”. Management Science 6 (2): 187–190. doi:10.1287/mnsc.6.2.187.
• Leyzorek, M.; Gray, R. S.; Johnson, A. A.; Ladew, W. C.; Meaker, S. R., Jr.; Petry, R. M.; Seitz, R. N. (1957). Investigation of Model Techniques — First Annual Report — 6 June 1956 — 1 July 1957 — A Study of Model Techniques for Communication Systems. Cleveland, Ohio: Case Institute of Technology