最短路問題とは何？わかりやすく解説 Weblio辞書

最短路問題

　有向グラフ $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) という. 与えられたネットワークにおいて負の長さの有向閉路(負閉路と呼ぶ)が存在する場合には一般に最短路は存在しなくなる. ただし，負閉路を持つネットワーク上でも，初等的な（点を繰り返さない）道で最短なものを求める問題を考えることもあるが，一般的には解くことが難しい問題となる．

　一方, すべての枝の長さが非負の時に，より高速に最短路を見出すタイプの代表的なアルゴリズムとして, 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|)\,$ 時間のアルゴリズムとして実現可能である．

[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.

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

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

「OR事典」の他の用語

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