First Course in Combinatorial Optimization Oct. 29, 2007

2. Minimum-Weight Dipaths 2.1 No Negative-Weight Cycles Bellman-Ford Algorithm 2.2 All-Pairs Minimum-Weight Dipaths Floyd-Warshall Algorithm 2.3 Nonnegative Weights Dijkstra’s Algorithm 2.4 No Dicycles and Knapsack Programs

2. Minimum-Weight Dipaths 最短路問題 : 入力 : 有向グラフG, 枝のコスト関数c, 始点s, 終点t 出力 : 最短の(重み最小の)s-tパス パス：同じ節点を2度通らない枝の系列 -1 2 5 パスの重み 3 7 11 4 16 14 9 1

2.1 No Negative-Weight Cycles 最短路問題を高速に解く. 問題の入力に制限を加える. 　負の重みの閉路が存在しない 最短パス = 最短ウォーク 負閉路が存在 最短ウォーク問題は解を持たない 最短ウォーク問題を解けばよい 1 1 パス : 節点・辺の重複を許さない ウォーク : 節点・辺の重複を許す -5 -5

Minimum diwalks 最短ウォーク問題は高速に解ける(動的計画法). 本章では以下のような制限を設けた最短路問題を解く. 負の重みの閉路を持たない 負の重みの枝を持たない 閉路を持たない

Bellman-Ford Algorithm 入力 : 負閉路を持たない有向グラフG, 始点v. 出力 : vから他の全ての接点への最短路の重み. fk-1からfkを繰り返し求める. 最短路は最大でも|V|-2個の内点しか持たないので, が最短路の重みとなる. : 内点がk個以下である最短v-wパスの重み

Bellman-Ford Algorithm : 内点がk個以下である最短v-wパスの重み

Example b d 3 2 6 1 a 5 6 7 4 e 8 2 c f

Example 2 b d 3 2 6 1 a 5 6 7 4 e 8 2 k=0 8 c f

Example 2 5 b d 3 2 6 1 a 5 6 7 4 e 8 2 k=1 7 8 c f 8

Example 2 5 b d 3 2 6 11 1 a 5 6 7 4 e 8 2 k=2 6 7 c f 7 8

Example 2 5 b d 3 2 6 11 1 a 5 6 7 4 e 8 2 k=3 6 c f 6 7

Example 2 5 b d 3 2 6 11 1 a 5 6 7 4 e 8 2 k=4 6 c f 6

Computation time |V|回の繰り返しそれぞれで．各枝についてfkが更新される．

Finding Negative-Weight Cycle グラフが負閉路を含まない場合 : 最短路が含む内点は|V|-2個以下であるから， グラフが負閉路を含む場合は? グラフが始点sから到達可能な負閉路を含むならば， となる節点wが必ず存在する． 負閉路の検出に利用

proof. なるwが存在する．

2.2 All-Pairs Minimum-Weight Dipaths 出力 : 任意の2接点間の最短路の重み. fk-1からfkを繰り返し求める. （1つずつ節点を解放していく) 全ての節点を解放すれば最短路が求められるので、 　が最短路の重みとなる. 節点に1,2,･･･|V|の番号を付ける. 内点に1, …, kまでの節点だけを含む最短v-wパスの重み

Floyd-Warshall Algorithm 任意の全単射な写像 を選ぶ.

Computation time |V|回の繰り返し． 1回の繰り返しでO(|V|2)回の計算．

2.3 Nonnegative weights 入力 : 枝の重みが非負の有向グラフG, 始点v. 接点をP, Tの2つのクラスに分ける． Pは最短路がFixした節点．(Tはそれ以外) Tの接点を1つずつPに変えていく 節点が全てP : 　　　は最短v-wパスの重み : 内点が全てPである最短v-wパスの重み

Dijkstra’s Algorithm なるw*を選ぶ. なる全ての について,

Example b d 3 2 6 1 a 5 6 7 4 e 8 2 c f

Example 2 b d 3 2 6 1 a 5 6 7 4 e 8 2 8 c f

Example 2 5 b d 3 2 6 1 a 5 6 7 4 e 8 2 7 8 c f

Example 2 5 b d 3 2 6 11 1 a 5 6 7 4 e 8 2 6 7 c f 12

Example 2 5 b d 3 2 6 11 1 a 5 6 7 4 e 8 2 6 c f 6 12

Example 2 5 b d 3 2 6 11 1 a 5 6 7 4 e 8 2 6 c f 6

Example 2 5 b d 3 2 6 11 1 a 5 6 7 4 e 8 2 6 c f 6

Computation Time |V|回の繰り返し． 最小重みの節点を見つけるのにO(|V|)． f(v)の更新は合計で|E|回．

Correctness proof 前述のアルゴリズムで確かにv-wパスの最小重みが求められる事を示す. 2つの性質 が、各時点において成り立つ事を帰納法で示す.

Dijkstra’s Algorithm(再掲) 初期段階では なるw*を選ぶ. なる全ての について, は自明．

Induction ある時点で(a),(b)が成り立っていると仮定する． 現在のラベル : P,T, 次にTに変わる節点 : w* 次のラベル : P'=P+w*, T'=T-w* 次の(a')(b')が成り立つことを示す．

Induction P T v F1 k w*

Induction P' T' v j w w* w

2.4 No Dicycles and Knapsack Programs 閉路を持たない有向グラフ (DAG) 次のような全単射写像πを考える 1 2 3 4 5 右向きの枝しかない

No dicycles あるパスに含まれる接点をv1, ..., vmとすると、 : v-wパスの最小重み 　 : v-wパスの最小重み 節点wに対し， である全てのuについて f(u)がFixしていればf(w)も計算できる． という順に決定していけば良い．

Algorithm なるwについて, 各枝について1回f(w)の更新を行うので，

Example 5 2 2 3 3 2 1 ∞ 1 5 7 5 8 2 4 6 6 6

Kanpsack Problem

Example -11 空き : 25 空き : 6 空き : 0 -5 ・・・ -1 -1 -7

Example -11 空き : 25 空き : 0 -5 ・・・ -1 -1 -7

Conclusion 入力の制限 アルゴリズム 計算時間 負閉路なし Bellman-Ford 1始点 Floyd-Warshall 全点対 負の枝なし Dijkstra 閉路なし(DAG)