利用者:Fujimoto/最短路問題

【さいたんろもんだい (shortest path problem)】

概要

最短路問題は経路探索などの多くの応用を持ち, また他の最適化問題の子問題として用いられることも多く, 適用範囲の広い組合せ最適化問題である. そのため, 最短路問題を高速に解くことは重要な意味を持つ. 最短路問題に対する解法には, 安定的かつ効率的な高速なアルゴリズムが存在するが, 実問題は大規模(全米の道路ネットワークでは, 2400万点, 5800万枝にも及ぶ)になるため高速化が不可欠である.本解説では最短路問題の定義・種類を述べた後, 著名なアルゴリズムであるダイクストラ法に対する高速実装と実験結果等について説明を行う.

詳説

最短路問題の定義と種類

最短路問題は次のような問題である.

ある有向グラフ$G=(V,E)$ と各枝 $(v,w)\in E$ に重み $l(v,w)$ が付与されているネットワーク $N=(G,l)$ が与えられているとする. このとき有向グラフ $G$ の任意の 2 点 $s,t\in V$ に対し, 点 $s$ を始点とし, 点 $t$ を終点とする有向パス $p$ の中で, その長さ(パスに含まれる枝の重みの合計)が最小のパスを点 $s$ から点 $t$ への最短路 (shortest path) といい, 最短路を求める問題を最短路問題 (shortest path problem) という.

最短路問題は次のように 3 種類に分けることができる.

1対全(single-source)最短路問題

1点から全点に対する最短路と最短距離(最短路の長さ)を求める問題. 非負の枝の重みを持つグラフ上ではダイクストラ(Dijkstra)法が, 負の重みを持つ枝がある場合にはベルマン・フォード(Bellman-Ford)法が有名である.

全対全(all-pairs)最短路問題

全点間の最短路と最短距離を求める問題. ワーシャル・フロイド(Warshall-Folyd)法が有名であるが, 1対全最短路問題アルゴリズムを各点に対して適用することでも求めることができる.

1対1(point-to-point)最短路問題

2点間の最短路と最短距離を求める問題.

探索アルゴリズムと実装方法

最短路問題に関する探索アルゴリズムの中でも, 最も頻繁に利用されるダイクストラ法を取り上げ, アルゴリズムの説明から, 高速化のための優先キューの適用方法・実装方法について示していく.

ダイクストラ法

1959年, E. W. Dijkstraによって提案された1 対全最短路問題に対するアルゴリズムである. 探索するグラフ上の全ての枝の重みが非負でなければならないが, ベルマン・フォード法テンプレート:Ref に比べ効率的かつ高速である.ダイクストラ法は, ベルマン・フォード法と同じように動的計画法の一種とみなすことができるが, 点の探索の順序に特徴をもつ. 探索の途中で得られた始点 $s$ からの距離の最小値をポテンシャルもしくは距離ラベルとよび, その値の小さい順に点の探索を行い,最短路および最短距離を確定していく. つまり, 各点に対し, $d(s)=0,d(v)=+\infty (v\in V)$ とするポテンシャル $d$ を用意し, 探索点 $v$ に接続する枝 $(v,w)$ に対して, $d(v)+l(v,w)<d(w)$ ならば $d(w):=l(v,w)+d(v)$ とする操作を繰り返し行う. 終点 $t$ が探索点になった時点で終了させることで, 1対1最短路問題も効率的に求解可能である.