最短経路問題
提供: miniwiki
2017/3/5/ (日) 08:55時点におけるja>オランウータンによる版 (→最長単純道)
グラフ理論における最短経路問題（さいたんけいろもんだい、英: shortest path problem）とは、重み付きグラフの与えられた2つのノード間を結ぶ経路の中で、重みが最小の経路を求める最適化問題である。
Contents
種類
- 2頂点対最短経路問題
- 特定の2つのノード間の最短経路問題。一般的に単一始点最短経路問題のアルゴリズムを使用する。
- 単一始点最短経路問題（SSSP）
- 特定の1つのノードから他の全ノードとの間の最短経路問題。この問題を解くアルゴリズムとしては、ダイクストラ法やベルマン-フォード法がよく知られている。
- 全点対最短経路問題
- グラフ内のあらゆる2ノードの組み合わせについての最短経路問題。この問題を解くアルゴリズムとしては、ワーシャル-フロイド法が知られている。
このような分類がされているのは、後者の問題が単に前者の問題を初期条件（ノード）を変えて繰り返し解くのではなく、アルゴリズムの過程で得た情報を利用して計算量を減らすことが可能となるからでもある。
単一始点最短経路問題
辺の重みなし有向グラフ
| アルゴリズム | 計算量 | 作者 |
|---|---|---|
| 幅優先探索 | [math]O(E)[/math] |
辺の重みが非負値の有向グラフ
| アルゴリズム | 計算量 | 作者 |
|---|---|---|
| [math]O(V^2 EL)[/math] | Ford 1956 | |
| ベルマン-フォード法 | [math]O(VE)[/math] | Bellman 1958, Moore 1959 |
| [math]O(V^2 \log{V})[/math] | Dantzig 1958, Dantzig 1960, Minty (cf. Pollack & Wiebenson 1960), Whiting & Hillier 1960 | |
| ダイクストラ法（リスト） | [math]O(V^2)[/math] | Leyzorek et al. 1957, Dijkstra 1959 |
| ダイクストラ法（修正二分ヒープ） | [math]O((E+V) \log{V})[/math] | |
| . . . | . . . | . . . |
| ダイクストラ法（フィボナッチヒープ） | [math]O(E+V \log{V})[/math] | Fredman & Tarjan 1984, Fredman & Tarjan 1987 |
| [math]O(E \log{\log{L}})[/math] | Johnson 1982, Karlsson & Poblete 1983 | |
| Gabow 法 | [math]O(E \log{\frac{E}{V}} L)[/math] | Gabow 1983b, Gabow 1985b |
| [math]O(E+V \sqrt{\log{L}})[/math] | Ahuja et al. 1990 |
辺の重みが任意の実数の有向グラフ
| アルゴリズム | 計算量 | 作者 |
|---|---|---|
| ベルマン-フォード法 | [math]O(VE)[/math] | Bellman 1958, Moore 1959 |
漸化式
最短経路の距離は部分構造最適性が成立しており、下記漸化式が成立する。証明は『アルゴリズムイントロダクション』（ISBN 978-4764904088）などを参照。
- [math]V[/math] が頂点、[math]E[/math] が辺、[math]c(s, v)[/math] が辺の重み、[math]\mathrm{dist}(s, v)[/math] が最短経路の距離。[math]s, v, w \in V[/math]。[math]w \ne s[/math]。
- [math]\mathrm{dist}(s, s) = 0[/math] とおく。
- [math]\mathrm{dist}(s, w) = \min \{ \mathrm{dist}(s, v) + c(v, w) \mid (v, w) \in E \}[/math] が成立する。
単一始点の場合 [math]c(s, v) = 1[/math] なら幅優先探索が、[math]c(s, v) \ge 0[/math] ならダイクストラ法が、そうでないならベルマン-フォード法が使える。
ヒューリスティックスの併用
辺の重みが非負値の2頂点対最短経路問題で、最短経路の距離の下限値が分かっている場合はA*を使うと、ダイクストラ法よりも速く求まる。
応用
最短経路問題の身近な応用例には、鉄道の経路案内（駅すぱあと、駅探、NAVITIMEなど）がある。駅をノードとし、駅と駅の所要時間を重みとしたエッジとして、鉄道線路をグラフ化して最短経路を求めている。
類似問題
最長単純道
最短経路とは逆の問題で、最長単純道問題もある。最短経路の場合は、最短経路の部分問題もやはり最短経路であるが、最長単純道の場合、部分構造最適性が成立しておらず、貪欲法などで解くことが出来ない。辺の重みなしであっても、NP完全問題である。
最短閉路
- 巡回セールスマン問題 - グラフ内の全頂点を通り、始点に帰ってくる最短閉路を求める問題。NP困難であることが知られている。
- 中国人郵便配達問題 - グラフ内の全ての辺を1回以上通り、始点に帰ってくる最短閉路を求める問題。