2008-07-20
■[Graph][Algorithm] Dijkstra algorithm 
Dijkstra algorithm (ダイクストラ アルゴリズム)。
"全てのEdge(辺)のWeight(重み)が非負の場合"に、
重みつき有向グラフ G=(V,E) に対する
Single-Source Shortest-Path Problem (単一始点最短路問題)、を解くことができる。
実装の仕方により、Dijkstra algorithmの実行時間は Bellman-Ford algorithmより短くすることができる。
Dijkstra algorithmは、始点 s からの最終的な最短路重みが既に決まっているVertex(頂点)の集合 S を管理する。最小の最短路推定値 d[u] を持つ頂点 u ∈ V-S を選び、u を S に追加し、u から出る辺に対して、緩和操作 Relax の実施を繰り返す。
V-Sの全てのvertexを含み、最短路推定値 dの値をキーとする優先度つき Queue Qを管理する。
Dijkstra(G,w,s) 1. Initialize-Single-Source(G,s) 2. S ← φ 3. Q ← V[G] 4. while Q ≠φ 5. do u ← Extract-Min(Q) 6. S ← S ∪ {u} 7. for each vertex v ∈ Adj[u] 8. do Relax(u,v,w)
Initialize-Single-Source(G,s), Relax(u,v,w)はRelaxation(緩和操作)を参照
[実行時間(計算量)]
Dijkstra algorithmの実行時間は、"Min-Priority Queue(優先度つきmin-Queue)"の
実装方法に依存している。
(1) Initialize-Single-Source(G,s)は O(V),
[Min-Priority Queue操作]
(2) Insert(3行目)は、 |V|回 × Insert実行時間
(3) Extract-Min (5行目)は、 |V|回 × Extract-Min実行時間
(4) Decrease-Key(8行目 Relax)は、|E|回 × Decrease-Key実行時間
(For Loopの繰り返し数 |E|回)
・[Min-Priority Queueの実装例１：1から|V|に番号が振られた頂点を使用]
単に配列のv番目の位置に 最短路推定値 d[v] を記憶すればよい。
[2] Insertの実行時間 ... O(1)
[3] Extract-Minの実行時間 ... O(V)
[4] Decrease-Keyの実行時間 ...O(1)
⇒全体の実行時間 O(V^2 + E) = O(V^2)
・[Min-Priority Queueの実装例２：min-heapの使用]
グラフが十分に疎 (E =o(V^2 /logV))である場合の実用的な方法。
(2) Min-Heapの実現... O(V)
[3] Extract-Minの実行時間 ... O(logV)
[4] Decrease-Keyの実行時間 ...O(logV)
⇒全体の実行時間 O((V+E)logV)。
全ての頂点が、始点 s から到達可能な場合、O(E logV)
（E=o(V^2/logV)の場合における O(V^2)時間の改良）
・[Min-Priority Queueの実装例３：Fibonacci Heap(フィボナッチヒープ)の使用]
[3] Extra-Minのならし実行時間 ... O(logV)
[4] Decrease-Keyのならし実行時間...O(1)
⇒全体の実行時間 O(VlogV +E)
[Reference]:
Introduction to Algorithms, Second Edition
プログラミングコンテストチャレンジブック [第2...
2008-06-29
■[Graph][Algorithm] 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)
・Initialize-Single-Source(G,s),
Relax(u,v,w)
[計算量]
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
■[Graph][Algorithm] 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
2008-06-22
■[Graph][Algorithm] Relaxation 
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
■[Graph][Algorithm] Shortest-Path Problem 
"Shortest-Path Problem (最短路問題)"とは、
"最短路(shortest path)"を求める問題。
『vertex(頂点) u からvertex vへの最短路』とは
『経路重みが、最短路重みに等しい経路』。
。
※ここで、"辺重み","経路重み", "最短路重み"の定義は以下：
[辺重み]
Edge(辺)を、実数値のWeight(重み)に変換する関数 w：w: E →R
[経路重み]
経路 の 重みは、構成するEdgeの重みの和：
[最短路重み]
vertex uからvertex vへの最短路重み は、次のように定義される
(uからvへの経路が存在するとき)
(uからvへの経路が存在しないとき)
[Reference]:
Introduction to Algorithms, Second Edition
2008-06-15
■[Graph][Algorithm] Topological Sort 
Topological Sort (トポロジカル ソート)：
Directed Acyclic Graph（DAG：非循環有向グラフ) G=(V,E)に対し、
全vertexに対する線形順序で、G が edge (u, v) を含んでいれば、線形順序の中で uがvより先に現れる形へのVertex Sort。
Topological-Sort(G) 1. 各vertexの終了時刻 f[v]を計算するために、DFS(G)を呼び出す。 2. 終了vertexを連結リストの先頭に挿入する 3. retun vertexの連結リスト
[Reference]:
Introduction to Algorithms, Second Edition
■[Graph][Algorithm] Depth-First Search 
Depth-First Search (深さ優先検索).
(Reference："Introduction to Algorithms, Second Edition")
可能ならば常に"より深く"、グラフを探索する。
未探索の edge(辺) が残されている vertex(頂点) の中で、最後に発見した頂点vのedgeを探索。vのedge全て全てを探索し終えると、vを発見したときに通ったedgeを "Back track(後戻り)"し、直前のvertexから出る edgeを再探索する。
DFS(G) for each vertex u ∈ V[G] do color[u] ← WHITE π[u] ← NIL time ← 0 for each vertex u ∈ V[G] do if color[u]= WHITE then DFS-Visit(u) DFS-Visit(u) color[u] ← GRAY time ← time +1 d[u] ← time for each vetex v ∈ Adj[u] do if color[v] = WHITE THEN π[v] ← u DFS-Visit(v) color[u] ← BLACK f[u] ← time ← time+1
表記：
Adj[u]:vertex uの隣接 vertexリスト
π[u] :predecessor vertex (uの先行vertex)
d[u]: vertex uを発見した時刻
f[u]: vertex uの隣接リストAdj[u]を調べ終えた時刻
time: 1 から 2|Vertex数|の、整数
[color]
WHITE:発見前のvertex
GRAY :発見後の全処理終了前の
BLACK:隣接リスト Adj[u]を調べ終えた時刻
Depth-First Search DFS の計算量は、Θ(|V| + |E|)
[Reference]:
Introduction to Algorithms, Second Edition
アルゴリズムの設計と解析手法 (アルゴリズムイントロダクション)
2008-06-08
■[Graph][Algorithm] Moore, Breadth First Seach 
Edward F. Moore の Breadth First Seach Algorithm。
[Original]Edward F. Moore, "The shortest path through a maze": Proceedings of the International Symposium on the Theory of Switching, pages 285-292 Harvard University Press, 1959.
Algorithm MOORE [G=(V, E), s, e] 開始Vertex sから終了Vertex eへの、 接続グラフ G =(V,E)の最短路を決定するAlgorithm。 入力： ・開始Vetexを s、終了Vertexを e 全てのEdge (i,j)で長さl(i,j)=1の接続グラフを、G=(V,E)とする。 ・最初は全てのVertexにラベルがない。 出力： ・G=(V,E)の中の最短路 s → e 手続き： 1.sにラベル0をつける 2.i=0 とする。 3.ラベル iが付いているVertexに隣接する、 全てのラベル付けされていないVertexを検索する 4.見つかったVertexにラベル i+1 をつける 5.if(終了端 eにラベルがつけられた） ラベルの逆探索により、最短路を導出： k(eのラベル)、k-1, ..., 0とラベルを探索していき、 各該当Vertexを出力する。 else i=i+1 と増やし、Step 3へ戻る
計算量、メモリ使用量のOrderはそれぞれ次。
・計算量Order ...O(Edge数)
(sから順にVertexを移動し、隣接Vertexを検索していく手続きが、"2×Vetex回"行われる。)
・メモリ使用量Order...O(Vertex数)
(Vertexにつけるラベルの成分数)
巡回セースルマン問題(Traveling Salesman Problem)で、全てのEdge(辺)の長さが 1 の場合の解法。（※巡回セールスマン問題：与えられたグラフの最短Hamilton経路(グラフの全てのVertex(頂点)を通る経路)を決定する問題）
[Reference]:
Introduction to Algorithms, Second Edition
アルゴリズムの設計と解析手法 (アルゴリズムイントロダクション)
