《最短路問題》

出典: ORWiki

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

　有向グラフG=(V,A)\,の各枝a\in A\,に長さl(a)\in \mathbf{R}\,が付与されているネットワークN=(G=(V,A),l)\,が与えられているとする. 有向グラフG\,の任意の2点s,t\in V\,に対して, 点s\,を始点とし点t\,を終点とする有向道P\,の長さl(P)\,はP\,上の枝の長さの総和, \textstyle l(P)={\sum}_{a\in P}l(a)\,, と定める. 始点s\,から終点t\,への有向道P\,のなかで, その長さを最小にするもの(が存在すれば, それ)を点s\,から点t\,への最短路(shortest path)といい, 最短路を求める問題を最短路問題 (shortest path problem) という. 与えられたネットワークにおいて負の長さの有向閉路(負閉路と呼ぶ)が存在する場合には一般に最短路は存在しなくなる. ただし，負閉路を持つネットワーク上でも，初等的な（点を繰り返さない）道で最短なものを求める問題を考えることもあるが，一般的には解くことが難しい問題となる．

　最短路問題は組合せ最適化問題の中での最も基本的かつ重要な問題の一つである. 例えば, ナップサック問題, PERT, 巡回セールスマン問題など様々な組合せ最適化問題が最短路問題とも関係し, 最短路問題において得られた知識はそれらの組合せ最適化問題の解法にも影響を与えている. また, 交通計画や通信ネットワークの分野などでは最短路問題を利用し解析に必要な基本データを算出している. さらに, ネットワークフロー問題, 配送計画問題やネットワークデザインなどのより複雑な問題に対するアルゴリズムにおいて，子問題として最短路問題を解くことがしばしば要求され, その応用は広範囲におよぶ ([2]).

　最短路問題に対して様々なアルゴリズムが提案されている ([1, 6]). それらのアルゴリズムは, それが適用できるネットワークの種類から大きく二つに分類できる. 一つは, 負の長さの枝が存在しても適用できるアルゴリズムで, もう一つは, 負の長さの枝が存在しない時にのみ適用できるアルゴリズムである.

　前者のタイプのアルゴリズムとしては, L. R. Ford [5] とR. E. Bellman [3] によって独立に示されたベルマン・フォード法(Bellman-Ford algorithm)（フォード・ベルマン法ともいう）が良く知られている. この方法では, p(s)=0, p(v)=+\infty\, (v\in V)\,なる点のラベルp\,を用意して, 枝(u,v)\,に対してl(u,v)+p(u)<p(v)\,ならばp(v)\leftarrow l(u,v)+p(u)\,とおく．ここで，すべての枝に対して１回ずつこの操作を行うことを基本操作として，ラベルの減少が起る限り高々|V|\,回基本操作を繰り返す．基本操作が|V|\,回繰り返された場合には負閉路が検出される．そうでない場合には, 終了時に得られたラベルp\,によって，l(u,v)+p(u)-p(v)=0\,を満たす枝の全体からなるG\,の部分グラフ中の点s\,から各点v\,への有向道が最短路を与える．なお，ベルマン・フォード法の変種で隣接２点間の距離行列のべき乗と同等と見做される行列演算によって理解されるアルゴリズムとして，べき乗法(power method)も知られている. これらは{\rm O}(|V||A|)\,時間のアルゴリズムである．

　一方, すべての枝の長さが非負の時に，より高速に最短路を見出すタイプの代表的なアルゴリズムとして, E. W. Dijkstra [4] によって提案されたダイクストラ法 (Dijkstra's algorithm) が知られている.この方法では，出発点s\,からの(最短)距離が小さい順に最短路および(最短)距離が確定していく．初期ラベルP\,はベルマン・フォード法と同じで, アルゴリズム実行中に最短路が確定した点集合をW\,とすると，p(v)\, (v\in W)\,は点s\,から点v\,への(最短)距離に等しく, l(u,v)+p(u)-p(v)=0\,である枝(u,v)\,を通ってW\,内において点s\,から点v\,へ行く有向道が点s\,から点v\,への最短路である．W\,内で最後に(最短)距離が確定した点をu\,として, l(u,v)+p(u)<p(v)\,なる各点v\in V-W\,に対しp(v)\leftarrow l(u,v)+p(u)\,とおき，V-W\,中でラベルの最小な点v\,を見つけてW\leftarrow W\cup\{v\}\,とおく．初期にはW=\{s\}\,である．ダイクストラ法は{\rm O}(|A|+|V|\log|V|)\,時間のアルゴリズムとして実現可能である．

　ベルマン・フォード法やダイクストラ法など現在提案されている最短路問題に対するアルゴリズムは本質的に始点s\,から全点までの最短路を同時に求める. 全点間の最短路を求めたい場合には, １点から全点への最短路を求めるアルゴリズムを繰り返し適用し求めればよい．この場合, 負の長さの枝が存在する場合には１点からの最短路問題を１回解いてすべての枝の長さを非負に等価変換することが可能であり, 基本的にダイクストラ法を|V|\,回適用する手間で解くことができる．なお，全点間最短路問題の{\rm O}(|V|^3)\,時間のアルゴリズムであるワーシャル・フロイド法 (Warshall-Floyd algorithm) も知られている.

　最短路問題は有向グラフ上で定義されているが, 無向グラフ上の最短路問題を考えたい場合には, 各枝をそれと同じ長さの互いに逆向きの有向枝で置き換えることにより, 有向グラフの場合に帰着することができる．ただし，負の長さの枝が存在する場合は, この帰着によって負閉路が含まれるので, 通常の最短路問題には帰着されない．



参考文献

[1] R. K. Ahuja, T. L. Magnanti and J. B. Orlin, Network Flows:Theory, Algorithms, and Applications, Prentice Hall, New Jersey, 1993.

[2] R. K. Ahuja, T. L. Magnanti and J. B. Orlin, "Applications of Network Optimization," in Network Models, M. O, Ball, T. L. Magnanti, C. L. Monma and G. L. Nemhauser, eds., North-Holland, 1995.

[3] R. E. Bellman, "On a Routing Problem," Quarterly of Applied Mathematics, 16 (1958), 87-90.

[4] E. W. Dijkstra, "A note on two problems in connexion with graphs," Numerische Mathematik, 1 (1959), 268-271.

[5] L. R. Ford, Jr., "Network Flow Theory," Report P-923, Rand Corp., Santa Monica,1956.

[6] 久保，田村，松井 (編) 『応用数理計画ハンドブック』，朝倉書店，2002.

"http://www.orsj.or.jp/~wiki/wiki/index.php/%E3%80%8A%E6%9C%80%E7%9F%AD%E8%B7%AF%E5%95%8F%E9%A1%8C%E3%80%8B" より作成