最短路問題

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

概要

有向グラフの各枝に長さが付与されたネットワークにおいて, 指定された2点間の有向道の中で最短の長さをもつもの(最短路)を見出す組合せ最適化問題. ナップサック問題, PERT等様々な問題が最短路問題とも関係し, さらに, ネットワークフロー問題や配送計画等のより複雑な問題の子問題として出現することも多い. ダイクストラ法やベルマン・フォード法等を用いて解くことができる. 無向グラフに対しても同様に定義される.

詳説

　有向グラフ$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.

[7] アルゴリズムデータベース　http://www-or.amp.i.kyoto-u.ac.jp/algo-eng/db/