最短経路問題

提供: miniwiki
移動先:案内検索

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

種類

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完全問題である。

最短閉路

テンプレート:アルゴリズム