離散数学

最短経路問題落合 秀也

その前に・・・前回の話

深さ優先探索アルゴリズム
開始点sから 深さ優先探索を行うアルゴリズム
S.push(s)sWhile S is not empty
cv := S.pop()ab
If F[v] = false Then,ged
F[v] := truekf
Foreach node u in Adj[v]hS.push(u)ji
EndFor
EndIf
時間計算量：O(n+m)
EndWhile(*) 厳密には初期化処理が必要だが省略している2

その前に・・・前回の話

深さ優先探索アルゴリズム２

再帰呼び出しによる方法
深さ優先探索を行うアルゴリズム（再帰呼び出し版）

Function DFS(v)If F[v] = false Then,
F[v] := true
Foreach node u in Adj[v]DFS(u)
EndForEndIf
EndFunction

頂点sから探索を行う場合：

DFS(s)
を実行すれば良い

再帰呼び出しは、実際には、裏ではスタックを使って実行される

3

最短経路問題を考える• ラベル付(重み付)グラフ G=(V,E)が与えられたとき、頂点sから頂点tへの最短経路 s-t を求めたい• 辺のラベルの意味：• 地点間の道のり• 地点間の移動時間• 地点間の移動に要する燃料の量• 状態の遷移で失う資金

s

82222

94

5354471386

1=17t=18
8 8

154=23(*) 実際はコスト16の道が存在する• 最小コストでの移動経路を発見したい

4

最短経路問題の解法• ダイクストラ法• すべての辺の重みが非負の場合に適用可能• 貪欲法(Greedy Algorithm)の一種• ベルマン・フォード法• 辺の重みに負があっても良いケースがある（有向グラフで、有向閉路の和が負でない場合）• 動的計画法(Dynamic Programming)の一種
94-5s

5t-2

7

コストが、資金の支出の場合、マイナスは、収入を意味する

5ダイクストラ法(Dijkstra’s Algorithm)
1959年： Edsger Dijkstraによって考案された
a2 321sbe

H

231f

1

103

• 開始点 s∈Vから各頂点への最短経路を求める問題

g42266750 1c1d• 考え方 -- G(V,E)に対して74857 5i

赤字: 判明しているsからの最短距離h• いま、すでに部分Hに関して、最短経路が導出されているとする• sからの距離が判明している• Hと接する v ∈ V-H に対し、sからの距離を考える• その距離の最小値を与える
vを、Hに追加する
6ダイクストラ法(もう少し正確な定義)• 用語の定義：• グラフG(V,E)において、 u, v ∈V, e=(u,v) ∈ Eとする。
• 辺e=(u,v)の長さをleあるいはl(u,v)で表すとする。
• 開始点をsとする。d(u)で、sからuまでの最短距離を表すとする。
• prev(v)で、sからvへの最短経路におけるvの直前の頂点を表す。

• 挙動の定義： Vの部分集合 H を以下のように作成する。
• 初期状態： H = {s}, d(s)=0, d(v)=∞ (v≠s), prev(v)=null (v∈V) とする。
• u∈ H で辺e=(u, v)でつながっている v (∈ V-H) を考え、d’(v) = min e=(u,v):u∈H { d(u) + le }を計算する。
• v ∈ V-Hにおいて、上記をさらに最小化するvを選定し、そのvをHに追加し、その距離をd(v)とおき、その時のuを用いて、prev(v)=uとする。
d(u1)

d(u2)
H

l(u1,v1)d’(v1) = min {d(u)+le}l(u2,v2)d’(v2) = min {d(u)+le}d(v1)またはd(v2)のどちらか片方7を決定する練習• 以下のグラフに対し、ダイクストラ法により、頂点sから各頂点への最短経路とその距離を求めよ。
a28b1s1d36e55c1f

1422gh7455i8

解答：
a1s 0 122623f51473e5c158b6g

1d322

頂点h

7457i

5abcdefghi

最短経路sa

距離2sb1sc2sad5sbe3scf3sadg6sadgh7scfi79ダイクストラ法の実現：アルゴリズムの設計

素直に上述の定義に従って考えると・・・• 準備するもの• sからuまでの最小距離を格納する配列: d[u]• 初期条件: d[s]=0, (u≠sに対して) d[u]=∞• sからvへの最短経路で、vの直前を格納する配列: prev[v]• 初期条件: prev[v]=null• 辺の長さを与える関数: length(u,v)• 最短経路が確定した頂点のリスト: H• 初期条件: H = {s}• 方針d’(v) = min e=(u,v):u∈H { d(u) + le }• d’[v] を最小にする u∈H, v∈V-H の辺(u,v) を見つける• 見つかったら、prev[v]=u, d[v]=d’[v]とおき、vをHに追加する• 上記を、H=Vになるまで繰り返す
10

ダイクストラ法の実現：アルゴリズムの設計

工夫をしてみよう• 最短経路が確定した頂点のリスト(H)を考え、sからの距離d(v)が最小になるv (∈V-H)を、Hに追加していた（そして、これをH=Vになるまで繰り返した）。

• 最短経路が確定していない頂点のリスト(Q)を考え、sからの距離d(v)を最小にするv(∈Q)を、Qから削除する(そして、これをQが空になるまで繰り返す)。
• 各v(∈Q)において、d(v)の候補を常に計算できていれば、Qから削除される段階で d(v) が最小であれば、そこから新たにd(v)を計算をする必要はない。
11ダイクストラ法の実現: 二つのアプローチ
2a21s3H331f4

851s2

7 5c

その時点の周辺について計算
最小値を与える頂点を取り込む→671gd5be3231f1420 17i2 32110 he2g422a750 1c1db6610h74575Qi

最小値を与える頂点を除外する
12
除外された周辺の頂点までの距離を計算する

練習• もう一つのダイキストラ法(Qの中から最小値を与える頂点を取り除く方法)で、以下の頂点sから各頂点までの最短経路を求めよ。

a225sc1461db10h3811f5e 5i4j15g13

1. d[s]=0と置く。Qからはsが取り出される

a2 2 ∞c 4sに隣接する a, bの距離が計算される
2s∞

650∞
11∞e381 ∞∞df5∞∞h51i4j15∞b510∞g2. Qから、Qの中で最小のd(u)=2を与える a が取り出されるc∞24a24a に隣接する c, dの距離が計算される∞e 5 ∞ h2s056∞
7111 ∞∞df5b58∞i4j15∞

101g33. Qから、Qの中で最小のd(u)=4を与える c が取り出される

a2 2 4c に隣接する d, e の距離が計算される
2s0c657d118∞ e 5 ∞ h

4381 ∞∞

f51i4j15∞

b5∞

10g

4. Qから、Qの中で最小のd(u)=5を与える b が取り出される

a2b に隣接する d, g の距離が計算される

22s04 c 4 8e6567 d1 ∞∞1f5b53814∞

10∞h515 g

1∞ij155. Qから、Qの中で最小のd(u)=6を与える d が取り出される
d に隣接する f の距離が計算される
2sca2 2 40548e 5 ∞ h

78616d1

1 ∞∞

f5b531∞i4j1515 g

106. Qから、Qの中で最小のd(u)=7を与える f が取り出される
f に隣接する e, i, g の距離が計算される
2s0a2 2 45c8e 5 ∞ h

7866d1

1f5b54108

1 ∞411 g1531∞ij15

7. Qから、Qの中で最小の d(u)=8 を与える e が取り出される

a2 2 4e に隣接する h の距離が計算される

2s05c48 e 5 13∞h7866d11f5b51831∞i4j1511 g

108. Qから、Qの中で最小のd(u)=8を与える i が取り出される
i に隣接する h の距離が計算される
2s0a 2 2 4 c 4 8e566d1139 h
381711 8∞ijf5b5105411 g15

9. Qから、Qの中で最小の d(u)=9 を与える h が取り出される
h に隣接する j の距離が計算される

2s0a 2 2 4 c 4 8e566d11b57f5819h5831i412∞j1511 g

1010. Qから、Qの中で最小のd(u)=11を与える g が取り出される
g に隣接する j の距離が計算される
2s0a 2 2 4 c 4 8e566d11578f419h5831i

j15b5

1011 g1211. Qから、Qの中で最小の d(u)=12 を与える j が取り出される
j に隣接する 頂点はなし(Qの中で)
2s0

a 2 2 4 c 4 8e5616d15

最短経路

f4

1381i

12
j15b5

12. Qが空なので、終了
頂点

789h

511 g

10

距離asa2bsb5csac4dsbd6esace8fsbdf7gsbdfg

11hsbdfih9isbdfi8jsbdfihj122s0a 2 2 4 c 4 8e566d11578f419h5831ij15b51011 g12

装置 Q
d[u]
• Qの持つべきインタフェースを考察する• 初期化時：• QにVのすべてを投入する参照

add(v) : v∈VisEmpty() ?
• 実行時：• Qが空かどうかを判定する
changeKey()• Qから、d(u)を最小とするuを取り出す• Qの内部をdで整理する (Qがヒープの場合)

Q20

ダイクストラのアルゴリズム
Foreach v∈Vd[v] := ∞, prev[v] :=nullQ.add(v)EndFord[s] :=0a2sb11d3862eg
41725
While Q is not empty
u := Q.extractMin()
45c51
Foreach v in Adj[u]If d[v] > d[u] + length(u, v) Then,i5d[v] := d[u] + length(u, v)
fprev[v]=u( Q.changeKey() -- if the implementation of Q is a heap )EndIf
EndFor21EndWhilehダイクストラ法:
計算量の考察While Q is not empty
u := Q.extractMin()
Foreach v in Adj[u]If d[v] > d[u] + length(u, v) Then,d[v] := d[u] + length(u, v)• While文の内部は n回実行される。
prev[v]=u• Foreach文の内部は nm回実行される。
( Q.changeKey() ) 実装によっては O(nm) となりえる。 EndIf
EndForEndWhile• Q に リストや配列を使う場合• Q.extractMin()に O(n) の時間を要する• Q.extractMin()は n回 呼び出される O(n2)• Q に 2分ヒープを使う場合• Q.extractMin()に O(log n)の時間を要する• Q.extractMin()の呼び出しはn回ある  O(n log n)• d[v]の更新に伴うヒープの組換え処理に、O(log n)の時間を要する• d[v]の更新は、m回発生する  O(m log n)
 O( (n+m) log n )22

装置Qの実装１：リストを使った場合• Q.extractMin()
ポインタ p を用意
リストのすべての要素に対して、順にd(u)を計算
より小さいd(u)が発見されたら p に u へのポインタを設定する
すべての要素を確認したら、p の先を、リストから除外し、その値を返す
開始

abcdefd(u) =

2

12∞∞∞

p23

装置Qの実装２：ヒープを使った場合• 2分ヒープ• 親≦ 子の関係になるように構成された2分木• 根は最小となる

d[b]=1d[a]=2• Q.extractMin()

cd[e]=∞

d[d]=∞• dの変化に合わせて再構成を行う
 計算量 O(log n)d[c]=2a• 根を取り出し、再構成を行う
 計算量 O(log n)• Q.changeKey()bded[f]=∞f24

ベルマン・フォード法
Bellman Ford Algorithm
a5d32 28b10 1s2262c31f51410 73e56 g17475i

基本的な考え方• 開始点sからsへの距離を0とする• 各頂点の開始点sからの距離は、辺の重みを加算しながら、sから拡散するように伝搬させる。

h • 各頂点では距離の最小値を採用する。
5• 上記を、頂点数-1回行う

25

ベルマン・フォード法• i回目から、i+1回目への計算(漸化式)を考える• ここで、iは、拡散量(sから伝搬した辺の数)に相当する• i回目(i個の辺の伝搬を考えたとき)における、頂点sから頂点vまでの最短距離をOPT(i,v)とする。このとき、以下が言える。

OPT(i+1, v) = minu∈nbr(v) {OPT(i,u)+Cuv}(*) ここでnbr(v)は、vの近隣頂点(自分自身も含む)の集合とする
またCuvは辺(u,v)のコストとし、便宜上Cvv=0 とする。

• 初期条件 (i=0のとき)• OPT(0,s)=0, OPT(0,v)=∞ (v∈V, v≠s)

26

OPT(i+1, v) = minu∈nbr(v) {OPT(i,u)+Cuv}の意味
OPT(i,c)
OPT(i,b)

bc
Cbv

Cava
OPT(i,a)Ccvv

OPT(i,v)

Cvv (=0)

OPT(i,v)
OPT(i,a)+Cav
OPT(i,b)+Cbv
OPT(i,c)+Ccv
OPT(i+1,v)は、上記で最小のものとする
27

練習• 以下のグラフに対し、ベルマンフォード法により、頂点sから各頂点までの最短距離を求めよ。

a225sc1461db10h38

1

1f5

e 5i

4j15

g(*) ダイクストラ法との違いも考えてみよ28

1回目 0 2

a2

s

55c

2 ∞

56∞

1ds

2
555b5∞

1 ∞

fi

166c

4

j
15

4e 5∞

8
1 ∞

1 ∞

fi

10∞

1g∞

dh3

8
1 ∞

10

a2 2 4

0∞e∞

b

2回目

44h3∞

1j
15

g 15

29

2回目 0 2

a2 2 4
5s

5566

1s

2
555b

1

∞

1 ∞

fi

c66e 5

8
1 ∞
4

1d4
8

f10

h3∞

1j15

g 15

10

a2 2 404∞db

3回目c

8e 5 ∞ h
71 ∞ 1

4330

i

j15

g 1530

a2

3回目 0 25s

5524c6611dbs

2

20

555b8f8e 5 ∞ h
71 ∞ 1414c
661d10330

i

j15

g 15

10

a2

4回目

44

8e 5 13h

871 8 1

fi

4330
j15

g 1131

a2 2 4

4回目
s

2

0

55566

1

1dbs

2

2

0

555b4

8e 5 13h

871 8 1

fi

4

14c
661

d10330
j15

g 11

10

a2

5回目

c48e 5 9 h

871 8 1fi

4316j15

g 11

32

a2

5回目
s2

205554c
6611dbs

220555b8e 5 9 h

871 8 1fi

4

14c
661d10316j15

g 11

10a2

6回目

448e 5 9 h

871 8 1

fi

4312
j

15

g 11

33

6回目以降頂点 最短距離a 2 2 4cs

2

0555b

1

66d

148e 5 9 h

8

71 8 1

fi

4103j
15

g 1112abcdefghi
j25468711981234

ベルマンフォードのアルゴリズム
M[s]=0M[v]=∞, prev[v]=null (v∈V, v≠s)
For i=1, … , n-1// n=count(V)ad13g
Foreach e=(u, v) in E
If M[v] > M[u]+Ce8261
4M[v]=M[u]+Ce
12bs
prev[v]=uhe
EndIf
725EndFor
45c5EndFor
時間計算量: O(mn)1f5i35

ベルマンフォード法の分散化• グラフ G(V,E)において、各頂点は、辺で接続するもう片方の頂点と通信を行うものとする。
OPT(u) + Cuv• このとき、uv• 各頂点uから、頂点v (∈nbr(u))に向けて、OPT(u)+Cuvを発信する• 受信側の頂点vでは、受信した値の中(他者からのものも含む)で、最小のものをOPT(v)として選ぶ• 開始点sのOPT(s)は 0 に固定するという処理を行うと、ベルマンフォード法を分散的に実装できる36

ベルマンフォード法の分散化：
各頂点の動作OPT(u) + Cuv3

v2

u
OPT(u)

v3
頂点uからの送信(定期的に行う)

u1

u2

OPT(u3) + Cu3v

v1v
If OPT(v) > 受信結果
OPT(v) :=受信結果
EndIfu3

頂点vでの受信と処理
37

∞

da

7 2
31
1s3bc∞
31
10

7 23∞
∞

7 2331
1∞

07 2

31
103

13

1
1062∞

47 22
31
1034138

今後の予定6月10日： 休講 (レポートで代替)
6月17日: 最小全域木
6月24日: 最大流問題

39