最短路問題とは - OR事典 Weblio辞書

Weblio 辞書 > 学問 > OR事典 > 最短路問題の意味・解説

OR事典

最短路問題

概要

有向グラフの各枝に長さが付与されたネットワークにおいて, 指定された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/

「OR事典」の他の用語

組合せ最適化：	施設配置問題最大クリーク問題最小木問題最短路問題最適性の原理木板取り問題
グラフ･ネットワーク：	最大マッチング最小被覆定理最小木問題最小費用フロー問題最短路問題最近近傍法有向グラフ木

索引トップ用語の索引ランキングカテゴリー

最短路問題に関係した商品

【送料無料】データ構造とアルゴリズム / 杉原厚吉【単行本】HMV ローソンホットステーション R
【送料無料】数理計画法 TOKYO TECH BE-TEXT / 尾形わかは【単行本】HMV ローソンホットステーション R
【送料無料】アルゴリズムイントロダクション（第2巻）改訂2版楽天ブックス

>> 「最短路問題」を解説文に含む用語の一覧

>> 「最短路問題」を含む用語の索引

最短路問題のページへのリンク

最短路問題のページの著作権
Weblio 辞書情報提供元は参加元一覧にて確認できます。

1		井上和子
2		井上和子 (女優)
3		沓名環希
4		井上和子_(女優)
5		イノウエカズコ
6		行列のできる法律相談所
7		同居人カップルの殺人推理旅行
8		メガゾーン２３　PARTⅡ　秘密く・だ・さ・い
9		TPP
10		井上和子 (言語学者)

11		出不精
12		捗る
13		リーガル・ハイ
14		奇跡の人
15		福利厚生
16		アセスメント
17		自由民主党幹事長
18		先負
19		ハクビシン
20		クルーゾン症候群

21		石松千恵美
22		言葉
23		ダイバーシティ
24		タカラダニ
25		未満
26		土曜ワイド劇場
27		友引
28		ご指導ご鞭撻
29		セクシー・サイン　好き好き好き
30		女優


	Copyright (C) 2012 （社）日本オペレーションズ・リサーチ学会 All rights reserved.

最短路問題とは？

OR事典

最短路問題

概要

詳説

参考文献