2008-06-22

"Shortest-Path Problem (最短路問題)"とは、
"最短路(shortest path)"を求める問題。

『vertex(頂点) u からvertex vへの最短路』とは
『経路重みが、最短路重みに等しい経路』。
　 $w(p) = \delta (u,v)$ 。

※ここで、"辺重み","経路重み", "最短路重み"の定義は以下：

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

[経路重み]
　経路 $p = < v_0, v_1, ..., v_k>$ の重みは、構成するEdgeの重みの和：
　 $w(p)= \sum_{i=1}^{k} w(v_{i-1}, v_{i})$

[最短路重み]
　vertex uからvertex vへの最短路重み $\delta (u,v)$ は、次のように定義される
　 $\delta (u,v)$
　 $= min \{w(p): u -> v \}$ (uからvへの経路が存在するとき)
　 $= \infty$ 　　　　　　　(uからvへの経路が存在しないとき)

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

Relaxation (緩和法)。

各Vertexの最短路重みの上界： d[v]

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

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

初期化：Initialize-Single-Source(G,s)

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

緩和操作：Relax(u,v,w)

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 Algorithmでの、緩和操作：

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

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

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

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