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