|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ ー ： [ちょうおん] (n) long vowel mark (usually only used in katakana) ・ 法 ： [ほう] 1. (n,n-suf) Act (law: the X Act)
ベルマン–フォード法 () は、重みつき有向グラフにおける単一始点の最短経路問題を解くラベル修正アルゴリズムの一種である。各辺の重みは負数でもよい。辺の重みが非負数ならば優先度つきキューを併用したダイクストラ法の方が速いので、ベルマン–フォード法は辺の重みに負数が存在する場合に主に使われる。名称は開発者であるリチャード・E・ベルマンと Lester Ford, Jr. にちなむ。 グラフに「負閉路」(negative cycle) が含まれるとき、すなわち辺の重みの総和が負になるような閉路が存在するとき、好きなだけ小さな重みを持つ歩道を取れるので、「最短」経路は定まらない。このためベルマン-フォード法も負閉路が始点から到達可能である場合は正しい答を出せないが、負閉路を検出してその存在を報告することはできる。 ロバート・セジウィックによれば、「負の重みは単なる数学的な好奇心の対象というだけではない。（中略）他の問題を最短経路問題に還元すると、自然に負の重みが現れる」〔Robert Sedgewick. Algorithms in Java. Third Edition. ISBN 0-201-36121-3. Section 21.7: Negative Edge Weights. http://safari.oreilly.com/0201361213/ch21lev1sec7〕。''G'' を負閉路を含むグラフとしよう。最短経路問題のとあるNP完全な変種で、''G'' における辺の重複を許さない（負閉路を含む）最短経路を求めよという問題がある。セジウィックはハミルトン閉路問題をこの問題に還元する方法を示している。 == アルゴリズム == ベルマン–フォード法の基本構造はダイクストラ法とよく似ているが、ダイクストラ法が総当り的に未処理の重みが最小のノードを選択して緩めるのに対して、ベルマン–フォード法は頂点数を |''V''|としたとき、全辺を緩めることを単に|''V''| − 1 回繰り返す（初期状態で始点以外の頂点の始点からの距離は無限大にしておき、処理の途中段階で各頂点の始点からの最短距離と思われる距離に置き換えていく。これを relaxing（=「緩める」「緩和」など）と称する）。負の閉路がなければ最短経路上の各頂点は高々1回しか出現しないので、反復によって最短距離が正確にグラフ全体に伝播する。重みが正であることを前提とした構造上の仮定に基づく貪欲法的手法とは異なり、この直接的な方法はより汎用的である。 ベルマン–フォード法の実行時間は ''O''(|''V''|·|''E''|) で、|''V''|と|''E''|はそれぞれ頂点数と辺数である。 procedure BellmanFord(''list'' vertices, ''list'' edges, ''vertex'' source) ''// この実装では、グラフを頂点のリストと辺のリストで表す。'' ''// そして、各頂点の ''distance'' と ''predecessor'' 属性が'' ''// 最短経路を格納するよう変更していく。'' ''// Step 1: グラフの初期化'' for each vertex v in vertices: if v is source then v.distance := 0 else v.distance := infinity v.predecessor := null ''// Step 2: 辺の緩和を反復'' for i from 1 to size(vertices) - 1: for each edge uv in edges: ''// uv は u から v に向かう辺'' u := uv.source v := uv.destination if v.distance > u.distance + uv.weight: v.distance := u.distance + uv.weight v.predecessor := u ''// Step 3: 負の重みの閉路がないかチェック'' for each edge uv in edges: u := uv.source v := uv.destination if u.distance + uv.weight < v.distance: error "Graph contains a negative-weight cycle" 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「ベルマン–フォード法」の詳細全文を読む スポンサード リンク
|