Bellman-Ford algorithm

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
アルゴリズムの設計と解析手法 (アルゴリズムイントロダクション)

DAG-Shortest-Paths algorithm

DAG-Shortest-Paths algorithm
(有向非巡回グラフ 最短路アルゴリズム)。

有向非巡回グラフ(DAG: Directed Acyclic Graph)の最短路を求めるアルゴリズム。

DAG G =(V,E)のEdgeに対し次の操作を行う：

1. DAG G に対し、Topological sortを行い、
　 線形順序を与える。
　（⇒ vertex u から vertex v への経路があれば u が v に先行する。）

2. 与えられた線形順序の順に、各 veretex vに対し一度、
　 Relaxation(緩和操作) を実行する。

負の重みのEdgeがあっても、DAGには 負の重みに閉路は存在しないので、
最短路はDAG上では、常に明確に定義されている。

DAG-Shortest-Paths(G,w,s)
　Topological-Sort(G)
　Initialize-Single-Source(G,s)
　for each vertex u (Topological sortの順に)
　　do for each vertex v ∈ Adj[u]
　　　do Relax(u,v,w)

ここで、
Adj[u] : vertex uの隣接 vertexリスト

また、次の各関数の内容は次を参照：
・Topological-Sort(G)
　⇒ Topological Sort
・Initialize-Single-Source(G,s),
　Relax(u,v,w)
　⇒Relaxation

[計算量]

DAG-Shortest-Paths algorithm の計算時間は、Θ(V+E)。

次であるため：
(1) Topological-Sort(G)の計算時間は、Θ(V+E)。
(2) Initialize-Single-Source(G,s)の計算時間は、Θ(V)。
(3) for LoopはVertexごとに1回の操作を行い、E回繰り返される、
　　また、内部 for Loopは Θ(1)時間で実行されるので、このLoopの計算時間は、Θ(E)。

※この実行時間は、グラフの隣接リストのサイズに対して線形。

[関連]
PERT chart の Critical-Path算出：
Critical-Pathとは、有向非巡回グラフの最長路。
順序列を実行するのに要する最長時間に対応する。
Critical Pathの経路重みは、全てのJobを実行するのに要する時間の下界になる。

次のどちらかの変換、算出方法で算出できる。

・Edge の重みを負にし、DAG-Shortest-Path(G,w,s)を実行

・Initialize-Single-Sourceの第2行で、"∞"を"−∞"に置き換え、
　Relax(u,v,w)で、">"を"<"で置き換えて、
　DAG-Shortest-Paths(G,w,s)、を実行。

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