Relaxation - hamadakoichi blog

Relaxation (緩和法)。

各vertex v∈V に関し、始点 sから、vへの最短路の重みに関する
上界 d[v]を、vertexの属性として管理する。

　d[v] ：最短路の推定値(shortest-path estimate)

Single-source shortest-path Problem (単一始点最短路問題)での、
最短路の推定値 d[v], 先行点 π(v)の初期化。
　s：始点vertex。

Initialize-Single-Source(G,s)
　for each vertex v ∈ V[G]
　　do d[v] ← ∞
　　　π[v] ← NIL
d[s] ←0

Edge (u,v)に関する緩和操作 Relax(u,v,w)。

これまで発見されている最短路を「vertex u を通ることにより改善できるか」を判定。
改善できるなら、vertex vの最短路推定値 d[v], 先行点 π[v]を更新する。

緩和操作により、d[v]が減少し、π[v]が更新されていく。

　w："Edge weight(辺重み)"。Edge(辺)を、実数値の重みに変換する関数(w: E →R)

Relax(u,v,w)
　if d[v] > d[u] + w(u,v)
　　then  d[v] ← d[u] + w(u,v)
　　　　 π[v] ← u

[操作]

初期化 "Initialize-Single-Source(G,s)"を呼び出し、
Edge (u,v)に対しする、緩和操作 "Relax(u,v,w)"を行っていく。
結果、各vertexに対し、最短路推定値 d[v], 先行vertex π[v]を、更新していくことができる。

Single-Source Shortest-path Problemの、解法の各Algorithmにごとに違うのは、
各Edgeに対し、
・緩和操作を実行する回数
・Edgeに対する緩和操作の順序。

[負の辺を許す一般的な単一始点最短路問題]
　・Bellman-Ford algorithm (ベルマン・フォードアルゴリズム)
　⇒Edgeごとに何度も緩和操作を行う。

[閉路を含まない有向グラフの最短路問題]：
　・Dijkstra algorithm (ダイクストラアルゴリズム)
　・DAG-shortest path algorithm (有向非巡回グラフ最短路アルゴリズム)
　⇒Edgeごとに1回の緩和操作