第25章 単一始点最短路 3節 Bellman-Fordのアルゴリズム アルゴリズムイントロダクション

Bellman-Fordのアルゴリズム Dijkstraのアルゴリズム ⇒ Bellman-Fordのアルゴリズムの提案 動作時間は 前提として，各辺の重みが正であった． 実際は重みが負の閉路が無ければ最短路木は構成可能． 重みが負の辺があっても動くアルゴリズムがあればより一般的なグラフに適用可能． ⇒　Bellman-Fordのアルゴリズムの提案

Bellman-Fordのアルゴリズム 基本的にはDijkstraのアルゴリズムと同じ． 1 2 3 4 5 6 7 8 ∞ ∞ ∞ ∞ ∞

Bellman-Fordのアルゴリズム 基本的にはDijkstraのアルゴリズムと同じ． ∞ 緩和は辞書順に行う ∞ ∞ ∞ ∞ 1 2 3 4 5 6 7 8 ∞ ∞ ∞ ∞ ∞

Bellman-Fordのアルゴリズム 基本的にはDijkstraのアルゴリズムと同じ． 緩和は辞書順に行う ∞ この図は(s,t)から初めて(t,w)まで見た状況 1 2 3 4 5 6 7 8 ∞

Bellman-Fordのアルゴリズム 基本的にはDijkstraのアルゴリズムと同じ． 次々と確認していき，緩和をしていく． ∞ 1 2 3 4 5 6 7 8 ∞

Bellman-Fordのアルゴリズム 基本的にはDijkstraのアルゴリズムと同じ． 次々と確認していき，緩和をしていく． 1 2 3 4 5 6 7 8

Bellman-Fordのアルゴリズム 基本的にはDijkstraのアルゴリズムと同じ． 次々と確認していき，緩和をしていく． 1 2 3 4 5 6 7 8

Bellman-Fordのアルゴリズム 基本的にはDijkstraのアルゴリズムと同じ． 次々と確認していき，緩和をしていく． 1 2 3 4 5 6 7 8

Bellman-Fordのアルゴリズム 基本的にはDijkstraのアルゴリズムと同じ． 緩和されきった各節点の重みが，その隣接した重みから計算されるものから適切か判断． 1 2 3 4 5 6 7 8

Bellman-Fordのアルゴリズムの正当性 補題25.12 　　は始点sと重み関数　　　　 を持つグラフで，sから到達可能な閉路が存在しないとき， 　　　　　 が終了した時にはsから到達可能なすべての頂点vに対して が成り立つ． 証明

Bellman-Fordのアルゴリズムの正当性 系25.13 　　は始点sと重み関数　　　　 を持つグラフとする．このとき， を適用した　に対し，各頂点　　 に対して， 証明 　⇒　補題25.13より，自明 　⇐　i番目の緩和で　　　　となったとすると，　に辺を伸ばす頂点　は　　 番目までの緩和で 　　　　となり，それを繰り返すと　から　への経路が存在する事が言える．

Bellman-Fordのアルゴリズムの正当性 定理25.14 　　は始点sと重み関数　　　　 を持つグラフに 　を適用したとき， 1)　が　から到達可能な不の重みの閉路を含んでいないとき，trueを返し，すべての　　 に対して 　　　　　が成り立ち，先行点グラフ　 は　を根とする最短路木となる． 2)　が　から到達可能な不の重みの閉路を含んでいるとき，falseを返す．

Bellman-Fordのアルゴリズムの正当性 定理25.14 証明はDijkstra法の時と同じ．trueを返すか，falseを返すかを確認する． 1)　到達可能な閉路が存在しない場合． ループでfalseを返すことは 無いのでtrueを返す． 1 2 3 4 5 6 7 8

Bellman-Fordのアルゴリズムの正当性 定理25.14 2)　到達可能な負の重みの閉路　　　　　　　　が存在する場合．trueを返すとするなら，　　　　　　　　　 より， ここで，　　　　　　　　より， 　　　　　　　となり，矛盾． よってfalseを返す． 1 2 3 4 5 6 7 8

閉路の無い有向グラフでの単一始点最短路 これまでの手法は全て 時間かかっていた． 閉路が無い状況では 時間で可能 ⇒トポロジカルソートの利用 これまでの手法は全て　　時間かかっていた． 閉路が無い状況では　　　　時間で可能 ⇒トポロジカルソートの利用 有向グラフの流れが分かれば，到達不可能な節点，緩和すべき順番が分かる 結果的に走査が一回で済む．

閉路の無い有向グラフでの単一始点最短路 トポロジカルソートの利用 1 2 3 4 5

閉路の無い有向グラフでの単一始点最短路 トポロジカルソートの利用 1 2 3 4 5

閉路の無い有向グラフでの単一始点最短路 トポロジカルソートの利用 1 2 3 4 5

閉路の無い有向グラフでの単一始点最短路 トポロジカルソートの利用 1 2 3 4 5 頂点tから順番に走査を行う．

閉路の無い有向グラフでの単一始点最短路 トポロジカルソートの利用 1 2 3 4 5 頂点tから順番に走査を行う． 一周の走査で，最短路木が求まる．

Bellman-Fordのアルゴリズムの正当性 補題25.15 　　は始点sと重み関数　　　　 を持ち閉路を含まないならば，　　　　　　　が終了した時にすべての　　 に対して 　が成り立ち，先行点グラフ　は最短路木である． 証明 最短路　　　　　　　があるとして，トポロジカルソートの順に処理されるため，頭から順に緩和が行われている．帰納的に　　　　　 となり，この事実より　は最短路木．

閉路の無い有向グラフでの単一始点最短路 トポロジカルソートの利用 ジョブスケジューリング 確実に閉路が無い クリティカルパスは最長の経路 少量の変更で適用可能． 水洗い 切断 下茹で 炒め 1 2 3 4 5 煮込み 盛り付け

線形計画法への応用 線形計画法とは…？ 線形の制約式が存在 目的関数の値を最大化させるベクトルを考える．

線形計画法への応用 線形計画法は 最適解を求めるもの 実行可能解があるか無いかだけを判断するなら シンプレックス法等でほぼ多項式時間で解ける このような問題を実行可能判定問題という． このうち，各行が一つずつ1と-1を含むもの(連立差分制約式)は制約グラフで表現が可能である．

連立差分制約式 補題25.16 タスクスケジューリング等で利用可能． を連立差分制約式 の一つの解としたとき，任意の定数 に対して 　　　　　　　を連立差分制約式　　　の一つの解としたとき，任意の定数　に対して 　　も　　　の解である． 証明 　　　　　　　　　　　　　より明らか． タスクスケジューリング等で利用可能．

連立差分制約式 制約グラフ 連立差分制約式　　　において，　　の　を　個の頂点と　個の辺を持つグラフの接続行列として見る事ができる．

連立差分制約式 制約グラフ 各頂点に到達可能な事を保証するために，と　から各頂点への枝を追加する．

連立差分制約式 定理25.17 連立差分制約式　　　が与えられたとき，　　　を対応する制約グラフとする． が負の重みの閉路を含まなければ，　　　　　　　　　　　　　はこの連立制約式に対する実行可能解であり，負の重みの閉路を含むときは　　　　　　　　実行可能解は存在しない．　　　　

連立差分制約式 定理25.17 　 が負の重みの閉路を含まないとき， 　任意の辺　　　　において 　よって，　　　　と置く事で， 　制約式を全て満たす．　

連立差分制約式 定理25.17 が負の重みの閉路 を含むとき，閉路を構成する制約式を考えると， ・・・矛盾 つまり，制約式は満たされない． 　 が負の重みの閉路　　　　　　 を含むとき，閉路を構成する制約式を考えると， ・・・矛盾 つまり，制約式は満たされない． つまり，実行可能解は存在しない．