Bellman-Ford algorithm - hamadakoichi blog

Bellman-Ford Algorithm (ベルマン・フォードアルゴリズム)。
"負の重みの辺を許す"一般的な、
Single-Source Shortest-Path Problem (単一始点最短路問題)、を解くことができる。
"始点から到達可能な負の重みを持つ閉路が存在するかどうか"の判定も行う。
(存在する場合、Falseを返す。)

Bellman-Ford algorithmでも、緩和法を用い、Edgeごとに何度もRelaxation(緩和操作)を行う。
(一方、Dijkstra algorithm, DAG-shortest path algorithm、では Edgeごとに1回の緩和操作のみ。)
始点s から各頂点 v∈V への最短路の重みに関する推定値 d[v]を、
実際の最低路重み δ(s,v)になるまで順次、減らしていく。

Bellman-Ford(G,w,s)
　Initialize-Single-Source(G,s)
　for i ←1 to |V[G]|-1
　　do for each Edge (u,v) ∈ E[G]
　　　do Relax(u,v,w)
　for each Edge (u,v) ∈ E[G]
　　do if d[v] > d[u] + w(u,v)
　　　then return False
　return True

ここで、
・始点 Vertex s
・重み関数 w: E→R
・重みつき有向グラフ G=(V,E)

また、
・Initialize-Single-Source(G,s)
・Relax(u,v,w)
は Relaxation(緩和操作)を参照。

[計算量]

Bellman-Ford Algorithmの計算量は、O(VE)

次であるため：
(1) Initialize-Single-Source(G,s)は O(V),
(2) Edge に関する |V|-1回の走査はそれぞれ O(E)時間で実行される →合計 O(VE),
(3) 最後の閉路確認は、O(E),

※"始点から到達可能な負の重みを持つ閉路が存在するかどうか"の判定も行うため、(2)で、Edgeごとに数回の操作を行う。

[Reference]:
Introduction to Algorithms, Second Edition
アルゴリズムの設計と解析手法 (アルゴリズムイントロダクション)