グラフアルゴリズム - Gunma Universitykoichi/ALG2/7.2beamer.pdfグラフアルゴリズム山崎浩一理工学部電子情報理工学科アルゴリズムII, Autumn 2015

グラフアルゴリズム

山崎浩一

理工学部電子情報理工学科

アルゴリズム II, Autumn 2015

山崎浩一 (理工学部電子情報理工学科) グラフアルゴリズム Gunma Univ. 2015 1 / 16

諸定義

有向グラフ G = (V , E) において,各辺に重みが与えられているとする.

重みを決める関数を w : E → R とし,w の定義域をつぎのように [E ] から [G の上の経路の集合] に拡張する.

R は実数の集合である.各 i(1 ≤ i ≤ k) について, (vi−1, vi ) は E の要素である.p = (v0, v1, . . . , vk ) を G の上の経路とすると,この経路の重みは以下で定義される.

w(p) =k∑

i=1

w((vi−1, vi )).

辺の重み,経路の重みはそれぞれ辺の長さ,経路の長さともいう.

頂点 u から頂点 v への最短距離はつぎのように定義される.

δ(u, v){

min{w(p) | p は u から v への経路 } (u から v への経路が存在するとき)∞ (u から v への経路が存在しないとき)

単一頂点からの最短経路問題は G の始点の頂点 s から G のすべての頂点への最短距離と最短経路を求めることである.

−26

7

8−4

5

9

7

−3

a

b d

c e

−26

7

8−4

5

9

7

−3

a

b d

c e

w(a,b,e,d) = 6 + (−4) + 7 = 9w(a,b) = 6

−26

7

8−4

5

9

7

−3

a

b d

c e

δ(a,d) = 7 + (−3) = 4

図:重み付き有向グラフ,経路の重み,最短経路の例


諸定義




w(p) =k∑

i=1

w((vi−1, vi )).



δ(u, v){



−26

7

8−4

5

9

7

−3

a

b d

c e

−26

7

8−4

5

9

7

−3

a

b d

c e

w(a,b,e,d) = 6 + (−4) + 7 = 9w(a,b) = 6

−26

7

8−4

5

9

7

−3

a

b d

c e

δ(a,d) = 7 + (−3) = 4



諸定義




w(p) =k∑

i=1

w((vi−1, vi )).



δ(u, v){



−26

7

8−4

5

9

7

−3

a

b d

c e

−26

7

8−4

5

9

7

−3

a

b d

c e

w(a,b,e,d) = 6 + (−4) + 7 = 9w(a,b) = 6

−26

7

8−4

5

9

7

−3

a

b d

c e

δ(a,d) = 7 + (−3) = 4



諸定義




w(p) =k∑

i=1

w((vi−1, vi )).



δ(u, v){



−26

7

8−4

5

9

7

−3

a

b d

c e

−26

7

8−4

5

9

7

−3

a

b d

c e

w(a,b,e,d) = 6 + (−4) + 7 = 9w(a,b) = 6

−26

7

8−4

5

9

7

−3

a

b d

c e

δ(a,d) = 7 + (−3) = 4



諸定義




w(p) =k∑

i=1

w((vi−1, vi )).



δ(u, v){



−26

7

8−4

5

9

7

−3

a

b d

c e

−26

7

8−4

5

9

7

−3

a

b d

c e

w(a,b,e,d) = 6 + (−4) + 7 = 9w(a,b) = 6

−26

7

8−4

5

9

7

−3

a

b d

c e

δ(a,d) = 7 + (−3) = 4



各辺の重みが 1 のグラフに対する単一頂点からの最短経路問題

各辺の重みが 1 であるグラフの単一頂点からの最短経路は幅優先探索によって求めることができる.


Dijkstra のアルゴリズム (負の重みを持たないグラフ)

各辺の重みが非負であるグラフの単一頂点からの最短経路問題はつぎのアルゴリズムで解ける.このアルゴリズムは Dijkstra のアルゴリズム (文献 [B・3]) として知られており,貪欲アルゴリズムである.

dijkstra (G = (V , E), s, w)

Input: 負の重みの辺を持たないグラフ G,始点となる頂点 s,重み関数 w ;1 foreach u ∈ V do /* 初期化 */2 d [v ] := ∞; π[v ] := nil ;

3 d [s] := 0 ; C := V ; /* C は未確定頂点の集合を表す */4 while C ̸= ∅ do5 u := C の中で d [·] が最小である要素の一つ ; /* u は確定してよい */6 C := C − {u} ; /* 未確定の頂点が減っていく */7 foreach (u, v) ∈ E なる v do /* 更新処理 */8 if d [v ] > d [u] + w(u, v) then9 d [v ] := d [u] + w(u, v); π[v ] := u ; /* d [v ] は単調減少 */


Dijkstra のアルゴリズム (負の重みを持たないグラフ)


Input: 負の重みの辺を持たないグラフ G,始点となる頂点 s,重み関数 w ;foreach u ∈ V do /* 初期化 */

d [v ] := ∞; π[v ] := nil ;

d [s] := 0 ; C := V ; /* C は未確定頂点の集合を表す */while C ̸= ∅ do

u := C の中で d [·] が最小である要素の一つ ; /* u は確定してよい */C := C − {u} ; /* 未確定の頂点が減っていく */foreach (u, v) ∈ E なる v do /* 更新処理 */

if d [v ] > d [u] + w(u, v) thend [v ] := d [u] + w(u, v); π[v ] := u ; /* d [v ] は単調減少 */

V−C

確定

未確定

V

C

1

5

4 3

2

10 50

100 30

20

50

510

1

5

4 3

2

10 50

100 30

20

50

510

1

5

4 3

2

10 50

100 30

20

50

510

1

5

4 3

2

10 50

100 30

20

50

510

1

5

4 3

2

10 50

100 30

20

50

510

35分後30分後20分後10分後

図: Dijkstra アルゴリズムのイメージ


Dijkstra のアルゴリズムの実効例 (P134)

dijkstra (G = (V ,E), s, w)


d [v ] := ∞; π[v ] := nil ;




a

b

cd

e

0

∞

∞∞

∞

0

50

30100

10

0

50

3020

10

0

40

3020

10

0

35

3020

10

50

30100

10

5

50

2010

▷

▷

▷

a

e

d c

b

ステップ u C d π0 {1, 2, 3, 4, 5} [0,∞,∞,∞,∞] [nil, nil, nil, nil, nil]

1 1 {2, 3, 4, 5} [0, 50, 30, 100, 10] [nil, 1, 1, 1, 1]2 5 {2, 3, 4} [0, 50, 30, 20, 10] [nil, 1, 1, 5, 1]3 4 {2, 3} [0, 40, 30, 20, 10] [nil, 4, 1, 5, 1]4 3 {2} [0, 35, 30, 20, 10] [nil, 3, 1, 5, 1]5 2 ∅ [0, 35, 30, 20, 10] [nil, 3, 1, 5, 1]





d [v ] := ∞; π[v ] := nil ;




a

b

cd

e

0

∞

∞∞

∞

0

50

30100

10

0

50

3020

10

0

40

3020

10

0

35

3020

10

50

30100

10

5

50

2010

▷

▷

▷

a

e

d c

b

ステップ u C d π0 {1, 2, 3, 4, 5} [0,∞,∞,∞,∞] [nil, nil, nil, nil, nil]

1 1 {2, 3, 4, 5} [0, 50, 30, 100, 10] [nil, 1, 1, 1, 1]2 5 {2, 3, 4} [0, 50, 30, 20, 10] [nil, 1, 1, 5, 1]3 4 {2, 3} [0, 40, 30, 20, 10] [nil, 4, 1, 5, 1]4 3 {2} [0, 35, 30, 20, 10] [nil, 3, 1, 5, 1]5 2 ∅ [0, 35, 30, 20, 10] [nil, 3, 1, 5, 1]





d [v ] := ∞; π[v ] := nil ;




a

b

cd

e

0

∞

∞∞

∞

0

50

30100

10

0

50

3020

10

0

40

3020

10

0

35

3020

10

50

30100

10

5

50

2010

▷

▷

▷

a

e

d c

b

ステップ u C d π0 {1, 2, 3, 4, 5} [0,∞,∞,∞,∞] [nil, nil, nil, nil, nil]1 1 {2, 3, 4, 5} [0, 50, 30, 100, 10] [nil, 1, 1, 1, 1]

2 5 {2, 3, 4} [0, 50, 30, 20, 10] [nil, 1, 1, 5, 1]3 4 {2, 3} [0, 40, 30, 20, 10] [nil, 4, 1, 5, 1]4 3 {2} [0, 35, 30, 20, 10] [nil, 3, 1, 5, 1]5 2 ∅ [0, 35, 30, 20, 10] [nil, 3, 1, 5, 1]





d [v ] := ∞; π[v ] := nil ;




a

b

cd

e

0

∞

∞∞

∞

0

50

30100

10

0

50

3020

10

0

40

3020

10

0

35

3020

10

50

30100

10

5

50

2010

▷

▷

▷

a

e

d c

b

ステップ u C d π0 {1, 2, 3, 4, 5} [0,∞,∞,∞,∞] [nil, nil, nil, nil, nil]1 1 {2, 3, 4, 5} [0, 50, 30, 100, 10] [nil, 1, 1, 1, 1]

2 5 {2, 3, 4} [0, 50, 30, 20, 10] [nil, 1, 1, 5, 1]3 4 {2, 3} [0, 40, 30, 20, 10] [nil, 4, 1, 5, 1]4 3 {2} [0, 35, 30, 20, 10] [nil, 3, 1, 5, 1]5 2 ∅ [0, 35, 30, 20, 10] [nil, 3, 1, 5, 1]





d [v ] := ∞; π[v ] := nil ;




a

b

cd

e

0

∞

∞∞

∞

0

50

30100

10

0

50

3020

10

0

40

3020

10

0

35

3020

10

50

30100

10

5

50

2010

▷

▷

▷

a

e

d c

b

ステップ u C d π0 {1, 2, 3, 4, 5} [0,∞,∞,∞,∞] [nil, nil, nil, nil, nil]1 1 {2, 3, 4, 5} [0, 50, 30, 100, 10] [nil, 1, 1, 1, 1]2 5 {2, 3, 4} [0, 50, 30, 20, 10] [nil, 1, 1, 5, 1]

3 4 {2, 3} [0, 40, 30, 20, 10] [nil, 4, 1, 5, 1]4 3 {2} [0, 35, 30, 20, 10] [nil, 3, 1, 5, 1]5 2 ∅ [0, 35, 30, 20, 10] [nil, 3, 1, 5, 1]





d [v ] := ∞; π[v ] := nil ;




a

b

cd

e

0

∞

∞∞

∞

0

50

30100

10

0

50

3020

10

0

40

3020

10

0

35

3020

10

50

30100

10

5

50

2010

▷

▷

▷

a

e

d

c

b

ステップ u C d π0 {1, 2, 3, 4, 5} [0,∞,∞,∞,∞] [nil, nil, nil, nil, nil]1 1 {2, 3, 4, 5} [0, 50, 30, 100, 10] [nil, 1, 1, 1, 1]2 5 {2, 3, 4} [0, 50, 30, 20, 10] [nil, 1, 1, 5, 1]

3 4 {2, 3} [0, 40, 30, 20, 10] [nil, 4, 1, 5, 1]4 3 {2} [0, 35, 30, 20, 10] [nil, 3, 1, 5, 1]5 2 ∅ [0, 35, 30, 20, 10] [nil, 3, 1, 5, 1]





d [v ] := ∞; π[v ] := nil ;




a

b

cd

e

0

∞

∞∞

∞

0

50

30100

10

0

50

3020

10

0

40

3020

10

0

35

3020

10

50

30100

10

5

50

2010

▷

▷

▷

a

e

d

c

b

ステップ u C d π0 {1, 2, 3, 4, 5} [0,∞,∞,∞,∞] [nil, nil, nil, nil, nil]1 1 {2, 3, 4, 5} [0, 50, 30, 100, 10] [nil, 1, 1, 1, 1]2 5 {2, 3, 4} [0, 50, 30, 20, 10] [nil, 1, 1, 5, 1]3 4 {2, 3} [0, 40, 30, 20, 10] [nil, 4, 1, 5, 1]

4 3 {2} [0, 35, 30, 20, 10] [nil, 3, 1, 5, 1]5 2 ∅ [0, 35, 30, 20, 10] [nil, 3, 1, 5, 1]





d [v ] := ∞; π[v ] := nil ;




a

b

cd

e

0

∞

∞∞

∞

0

50

30100

10

0

50

3020

10

0

40

3020

10

0

35

3020

10

50

30100

10

5

50

2010

▷

▷

▷

a

e

d c

b

ステップ u C d π0 {1, 2, 3, 4, 5} [0,∞,∞,∞,∞] [nil, nil, nil, nil, nil]1 1 {2, 3, 4, 5} [0, 50, 30, 100, 10] [nil, 1, 1, 1, 1]2 5 {2, 3, 4} [0, 50, 30, 20, 10] [nil, 1, 1, 5, 1]3 4 {2, 3} [0, 40, 30, 20, 10] [nil, 4, 1, 5, 1]

4 3 {2} [0, 35, 30, 20, 10] [nil, 3, 1, 5, 1]5 2 ∅ [0, 35, 30, 20, 10] [nil, 3, 1, 5, 1]





d [v ] := ∞; π[v ] := nil ;




a

b

cd

e

0

∞

∞∞

∞

0

50

30100

10

0

50

3020

10

0

40

3020

10

0

35

3020

10 50

30100

10

5

50

2010

▷

▷

▷

a

e

d c

b

ステップ u C d π0 {1, 2, 3, 4, 5} [0,∞,∞,∞,∞] [nil, nil, nil, nil, nil]1 1 {2, 3, 4, 5} [0, 50, 30, 100, 10] [nil, 1, 1, 1, 1]2 5 {2, 3, 4} [0, 50, 30, 20, 10] [nil, 1, 1, 5, 1]3 4 {2, 3} [0, 40, 30, 20, 10] [nil, 4, 1, 5, 1]4 3 {2} [0, 35, 30, 20, 10] [nil, 3, 1, 5, 1]

5 2 ∅ [0, 35, 30, 20, 10] [nil, 3, 1, 5, 1]





d [v ] := ∞; π[v ] := nil ;




a

b

cd

e

0

∞

∞∞

∞

0

50

30100

10

0

50

3020

10

0

40

3020

10

0

35

3020

10 50

30100

10

5

50

2010

▷

▷

▷

a

e

d c

bステップ u C d π

0 {1, 2, 3, 4, 5} [0,∞,∞,∞,∞] [nil, nil, nil, nil, nil]1 1 {2, 3, 4, 5} [0, 50, 30, 100, 10] [nil, 1, 1, 1, 1]2 5 {2, 3, 4} [0, 50, 30, 20, 10] [nil, 1, 1, 5, 1]3 4 {2, 3} [0, 40, 30, 20, 10] [nil, 4, 1, 5, 1]4 3 {2} [0, 35, 30, 20, 10] [nil, 3, 1, 5, 1]

5 2 ∅ [0, 35, 30, 20, 10] [nil, 3, 1, 5, 1]





d [v ] := ∞; π[v ] := nil ;




a

b

cd

e

0

∞

∞∞

∞

0

50

30100

10

0

50

3020

10

0

40

3020

10

0

35

3020

10 50

30100

10

5

50

2010

▷

▷

▷

a

e

d c


0 {1, 2, 3, 4, 5} [0,∞,∞,∞,∞] [nil, nil, nil, nil, nil]1 1 {2, 3, 4, 5} [0, 50, 30, 100, 10] [nil, 1, 1, 1, 1]2 5 {2, 3, 4} [0, 50, 30, 20, 10] [nil, 1, 1, 5, 1]3 4 {2, 3} [0, 40, 30, 20, 10] [nil, 4, 1, 5, 1]4 3 {2} [0, 35, 30, 20, 10] [nil, 3, 1, 5, 1]5 2 ∅ [0, 35, 30, 20, 10] [nil, 3, 1, 5, 1]





d [v ] := ∞; π[v ] := nil ;




a

b

cd

e

0

∞

∞∞

∞

0

50

30100

10

0

50

3020

10

0

40

3020

10

0

35

3020

10 50

30100

10

5

50

2010

▷

▷

▷

a

e

d c


0 {1, 2, 3, 4, 5} [0,∞,∞,∞,∞] [nil, nil, nil, nil, nil]1 1 {2, 3, 4, 5} [0, 50, 30, 100, 10] [nil, 1, 1, 1, 1]2 5 {2, 3, 4} [0, 50, 30, 20, 10] [nil, 1, 1, 5, 1]3 4 {2, 3} [0, 40, 30, 20, 10] [nil, 4, 1, 5, 1]4 3 {2} [0, 35, 30, 20, 10] [nil, 3, 1, 5, 1]5 2 ∅ [0, 35, 30, 20, 10] [nil, 3, 1, 5, 1]



ステップ u C d π0 {1, 2, 3, 4, 5} [0,∞,∞,∞,∞] [nil, nil, nil, nil, nil]1 1 {2, 3, 4, 5} [0, 50, 30, 100, 10] [nil, 1, 1, 1, 1]2 5 {2, 3, 4} [0, 50, 30, 20, 10] [nil, 1, 1, 5, 1]3 4 {2, 3} [0, 40, 30, 20, 10] [nil, 4, 1, 5, 1]4 3 {2} [0, 35, 30, 20, 10] [nil, 3, 1, 5, 1]5 2 ∅ [0, 35, 30, 20, 10] [nil, 3, 1, 5, 1]

1

5

4 3

2

10 50

100 30

20

50

510

1

5

4 3

2

10 50

100 30

20

50

510

1

5

4 3

2

10 50

100 30

20

50

510

1

5

4 3

2

10 50

100 30

20

50

510

1

5

4 3

2

10 50

100 30

20

50

510

35分後30分後20分後10分後

0

∞

10 50

100 30

20

50

510

0

10 50

10 50

100 30

20

50

510

0

20

10 50

100 30

20

50

510

0

30

10 50

100 30

20

50

510

∞ 5010

20

5010

100 30∞ ∞ 30

選択

更新

0

10 50

10 50

100 30

20

50

510

0

20

10 50

100 30

20

50

510

0

30

10 50

100 30

20

50

510

0

10 50

100 30

20

50

510

5010

20

4010

100 30 30

更新

更新更新

更新

更新

選択選択

3020

3510

更新

0

10 50

100 30

20

50

510

3020

3510

選択

図: Dijkstra のアルゴリズムの動き


補題 7.4 (P134)

最短路短経路に関して以下の補題が得られる (証明は演習問題 7.7).

補題 7.4

各辺に非負の重みが付けられている有向グラフ G について, p = (v0, v1, . . . vk ) を G の上の v0から vk への最短経路とする. 0 ≤ i < j ≤ k なる任意の i と j について, pij = (vi , vi+1, . . . vj ) はvi から vj への最短経路である.

jv

kv

iv

v0

図:補題 7.4 の意味するところ


補題 7.5 (P134)

最短路短経路に関して以下の補題が得られる.

補題 7.5

有向グラフ G の各辺は重み関数 w で非負の重みが付けられているとする. p を G の上の s からv までの最短経路とし, u をこの経路の v のーつ手前の頂点とすると

δ(s, v) = δ(s, v) + w(u, v)

u

v

s

δ(s,v)

δ(s,u)

w(u,v)

図:補題 7.5 の意味するところ


定理 7.1 (P135)

定理 7.1

G = (V , E) : 辺の重みが非負,有向グラフ, |V | = n

dijkstra の終了時では,∀v ∈ V , d [v ] = δ(s, v)

更新処理の d [v ] には s から v への実際に存在する経路での距離が格納される. したがって,δ(s, v) > d [v ] にはなり得ない.

更新処理

foreach (u, v) ∈ E なる v doif d [v ] > d [u] +w(u, v) then

d [v ] := d [u] + w(u, v) ;π[v ] := u ;

/* u は C から抜ける頂点 */

更新処理

foreach (u, v) ∈ E なる v do

if[現ベストでのv までの距離

]>

[現ベストでのu までの距離

]+ w(u, v) then[

現ベストでのv までの距離

]:=


]+ w(u, v) ;

[v の 1 つ手前] := u ;

よって,「u が C から抜けるとき, d [u] = δ(s, u)」を言えばよい.

C から抜けると (つまり d [u] = δ(s, u) となると),二度と d [u] は更新されない」も言える.

u が抜けるときの更新処理より, (u, v) ∈ E なる各 v に対し d [v ] ≤ d [u] + w(u, v) が成り立っている.その後は左辺 d [v ] は増加することは無く,右辺 d [u] + w(u, v) は変化することはない.


定理 7.1 (P135)

定理 7.1




更新処理


d [v ] := d [u] + w(u, v) ;π[v ] := u ;


更新処理



]>


]+ w(u, v) then[


]:=


]+ w(u, v) ;

[v の 1 つ手前] := u ;





定理 7.1 (P135)

定理 7.1




更新処理


d [v ] := d [u] + w(u, v) ;π[v ] := u ;


更新処理



]>


]+ w(u, v) then[


]:=


]+ w(u, v) ;

[v の 1 つ手前] := u ;





定理 7.1 (P135)

定理 7.1




更新処理


d [v ] := d [u] + w(u, v) ;π[v ] := u ;


更新処理



]>


]+ w(u, v) then[


]:=


]+ w(u, v) ;

[v の 1 つ手前] := u ;





定理 7.1 の帰納法による証明 (P135-136)

アルゴリズムは, s = u1, u2, . . . , un の順で C から抜いていったとする.この ui の添え字 i(つまり C のサイズ) に関する帰納法で示す.

初期段階: 一番最初に s が選ばれる,つまり u1 = s は問題ないであろう (負の重みが無いことも効いている:各自チェック). これから, d [s] = 0 = δ(s, s) を得る.

v ∈ V − C = {s = u1, u2, . . . , ui−1} に対しては, d [v ] = δ(s, v) が成り立つと仮定し, v = ui の場合を考える.

C = {v = ui , ui+1, . . . , un} に注意する. このとき (このタイミングで)v が選ばれたということから,

d [v ] = minw∈C

d [w ] (1)

P を s から v = ui へのある最短路とする.

ss ̸∈ C x y v v ∈ C

P の頂点で, C に属している最初の頂点を y とする. このときに y ∈ C に注意.(そのような y は存在する,実際 v ∈ C である. )

P 上での, y の 1 つ手前の頂点を x とする. このときに x ̸∈ C に注意.(そのような x は存在する,実際 s ̸∈ C である. )

したがって, P = s⇝P1

x → y⇝P2

v と書ける. (P1 と P2 は長さが 0 のパスかもしれない. )

d [y ] ≤ d [x ] + w(x, y) (x ̸∈ C と x が抜けるときの更新処理より)= δ(s, x) + w(x, y) (x ̸∈ C と帰納法の仮定より)≤ δ(s, x) + w(x, y) + δ(y, v) (負の重さの辺が無い i.e., δ(y, v) ≥ 0より)= δ(s, v) (P は s-v 間の最短路より)≤ d [v ] (δ(s, v) > d [v ] にはなり得ない)

一方, (1) と y ∈ C より d [v ] ≤ d [y ] なので,上記不等号がすべて等号になり, ui = v に対してもδ(s, v) = d [v ] が言えた.







d [v ] = minw∈C

d [w ] (1)






x → y⇝P2










d [v ] = minw∈C

d [w ] (1)






x → y⇝P2










d [v ] = minw∈C

d [w ] (1)






x → y⇝P2










d [v ] = minw∈C

d [w ] (1)






x → y⇝P2










d [v ] = minw∈C

d [w ] (1)






x → y⇝P2










d [v ] = minw∈C

d [w ] (1)






x → y⇝P2










d [v ] = minw∈C

d [w ] (1)






x → y⇝P2










d [v ] = minw∈C

d [w ] (1)






x → y⇝P2










d [v ] = minw∈C

d [w ] (1)






x → y⇝P2





Dijkstra のアルゴリズムの時間計算量 (P136)




(1 から 3 行目) while 文以前の操作全体は O(|V |) 時間でできる.

(4 行目) while 文のループは |V | 回まわる.

(5 行目) d が線形配列であれば, C の中から d [u] が最小である u を選ぶ操作は 1 回につき O(|V |) 時間必要である. この操作は |V | 回実行されるので,全体で O(|V |2) 時間あれば十分.

(7 から 8 行目)更新処理は∑u∈V

∑(u,v)∈E

【処理】という動きなので,全体で O(|E|) 時間必要である.

よって,手続き dijkstra の時間計算量は, d が線形配列のとき O(|V |2 + |E|) = O(|V |2) である.










∑(u,v)∈E












∑(u,v)∈E












∑(u,v)∈E












∑(u,v)∈E












∑(u,v)∈E




Dijkstra のアルゴリズムの効率化 (P136)




手続き dijkstra の 5 行目を実行するにあたり, C の各要素 u について d [u] を効率のよい優先順位付きキュー (ヒープ) の形で記録すると,このアルゴリズムの時間計算量はどうなるであろうか.

[d [u] が最小の頂点 u] が根にくるように作られたヒープを用いた場合:

ヒープの構成に O(|V |) 時間必要である. d [u] が最小である頂点 u を C から取り除いたあと,残りの木をヒープに整形するために O(log |V |) 時間必要である. これを頂点数回行う.また, (u, v) なる各頂点 v について, d [v ] の値が d [u] + w(u, v) に更新されるならば, d [v ] をヒープの上で適当な位置に移動 (percolate) する. この移動に要する時間も O(log |V |) である. 更新処理は |E| 回行われるので,上記移動を辺の本数数回行う.よって,この場合の全体の時間計算量は O(log |V |(|V | + |E|)) となる.有向グラフ G = (V , E) が疎のときは優先順位付きキューとしてヒープを用いる方が有利であるが, G が密な有向グラフの場合は各 d [v ] を線形配列で記憶した方が有利である.

フィボナッチヒープ (Fibonacciheap) を用いた場合:

時間計算量 O(|V | log |V | + |E|) で解ける.このアルゴリズムは Fredman と Tarjan によって考察された (文献 [B・7]).




























































































Bellman-Ford のアルゴリズム (負の閉路を持たないグラフ) (P137)

負の重みの辺を含む有向グラフの単一項点からの最短経路問題を考えよう.

Bellman-Ford のアルゴリズムはこの問題のアルゴリズムである (文献 [B・1], [B・5]).

ただし重みの和が負であるような閉路を含むとき,最短経路を決めることはできない.

このアルゴリズムでは与えられた重み付きの有向グラフについて,そのグラフに重みの和が負になる閉路が含まれるかどうかを検知し,

そのような閉路が含まれていれば,解は存在しないという答えが返り,そのような閉路が含まれていないときは,始点からのそれぞれの項点への最短経路と最短距離が与えられる.

Bellman-Ford (G = (V , E), w, s)

Input: 総和が負の閉路を持たないグラフ G,始点となる頂点 s,重み関数 w ;1 foreach u ∈ V do /* 初期化 */2 d [v ] := ∞; π[V ] := nil ;

3 d [s] := 0;;4 for i := 1 to |V | − 1 do /* |V | − 1 回で十分 */5 foreach (u, v) ∈ E do /* 任意の辺の順序で OK */6 if d [v ] > d [u] + w(u, v) then /* 更新処理 */7 d [v ] := d [u] + w(u, v); π[v ] := u;

8 foreach (u, v) ∈ E do /* 負の閉路のチェック */9 if d [v ] > d [u] + w(u, v) then

10 return “no solution”










































































Bellman-Fordアルゴリズムの正当性 (証明の概略)


Input: 総和が負の閉路を持たないグラフ G,始点となる頂点 s,重み関数w ;

1 foreach u ∈ V do /* 初期化 */2 d [v ] := ∞; π[V ] := nil ;

3 d [s] := 0;;4 for i := 1 to |V| − 1 do /* |V| − 1 回で十分 */5 foreach (u, v) ∈ E do /* 任意の辺の順序で OK */6 if d [v ] > d [u] + w(u, v) then /* 更新処理 */7 d [v ] := d [u] + w(u, v); π[v ] := u;



記号の導入

P(s, v) := {p | p は s から v への最短路 }.

|p| はパス p の辺の本数を表す.(w(p) でない!)

Li =

{v

∣∣∣∣ minp∈P(s,v)

|p| = i}

.

s

b a

c

35

1-23

s

b a

c

35

1-23

P(s, b) = {(s, a, b), (s, a, c, b)}

b ∈ L2, δ(s, b) = 4

図: Li の例









記号の導入



Li =

{v


|p| = i}

.

s

b a

c

35

1-23

s

b a

c

35

1-23

P(s, b) = {(s, a, b), (s, a, c, b)}

b ∈ L2, δ(s, b) = 4

図: Li の例









記号の導入



Li =

{v


|p| = i}

.

s

b a

c

35

1-23

s

b a

c

35

1-23

P(s, b) = {(s, a, b), (s, a, c, b)}

b ∈ L2, δ(s, b) = 4

図: Li の例

(s から到達できる) 負のサイクル無しの時

V =∪

1≤i≤|V|−1

Li に注意 (Li = ∅ もあり得る)

i 回目の for 文のループの終了時点で,各 v ∈ Liに対し d [v ] の値が確定する.

よって, (高々)|V | − 1 回の for 文のループで全ての頂点の値が確定する. さらにその後いくら for文を回しても for 文内の if 文を通ることはない.

1 回目のループ

0 ∞

∞ ∞

3

1

1 1

−1

図: アルゴリズムの実行例









記号の導入



Li =

{v


|p| = i}

.

s

b a

c

35

1-23

s

b a

c

35

1-23

P(s, b) = {(s, a, b), (s, a, c, b)}

b ∈ L2, δ(s, b) = 4

図: Li の例


V =∪

1≤i≤|V|−1





0 ∞

∞ ∞

3

1

1 1

−1










記号の導入



Li =

{v


|p| = i}

.

s

b a

c

35

1-23

s

b a

c

35

1-23

P(s, b) = {(s, a, b), (s, a, c, b)}

b ∈ L2, δ(s, b) = 4

図: Li の例


V =∪

1≤i≤|V|−1





0 ∞

∞ ∞

3

1

1 1

−1










記号の導入



Li =

{v


|p| = i}

.

s

b a

c

35

1-23

s

b a

c

35

1-23

P(s, b) = {(s, a, b), (s, a, c, b)}

b ∈ L2, δ(s, b) = 4

図: Li の例


V =∪

1≤i≤|V|−1





0 ∞

∞ ∞

3

1

1 1

−1










記号の導入



Li =

{v


|p| = i}

.

s

b a

c

35

1-23

s

b a

c

35

1-23

P(s, b) = {(s, a, b), (s, a, c, b)}

b ∈ L2, δ(s, b) = 4

図: Li の例


V =∪

1≤i≤|V|−1





0 ∞

∞ ∞

3

1

1 1

−1










記号の導入



Li =

{v


|p| = i}

.

s

b a

c

35

1-23

s

b a

c

35

1-23

P(s, b) = {(s, a, b), (s, a, c, b)}

b ∈ L2, δ(s, b) = 4

図: Li の例


V =∪

1≤i≤|V|−1





0 1

∞ ∞

3

1

1 1

−1










記号の導入



Li =

{v


|p| = i}

.

s

b a

c

35

1-23

s

b a

c

35

1-23

P(s, b) = {(s, a, b), (s, a, c, b)}

b ∈ L2, δ(s, b) = 4

図: Li の例


V =∪

1≤i≤|V|−1





0 1

∞ ∞

3

1

1 1

−1










記号の導入



Li =

{v


|p| = i}

.

s

b a

c

35

1-23

s

b a

c

35

1-23

P(s, b) = {(s, a, b), (s, a, c, b)}

b ∈ L2, δ(s, b) = 4

図: Li の例


V =∪

1≤i≤|V|−1





0 1

3 ∞

3

1

1 1

−1










記号の導入



Li =

{v


|p| = i}

.

s

b a

c

35

1-23

s

b a

c

35

1-23

P(s, b) = {(s, a, b), (s, a, c, b)}

b ∈ L2, δ(s, b) = 4

図: Li の例


V =∪

1≤i≤|V|−1





0 1

3 ∞

3

1

1 1

−1










記号の導入



Li =

{v


|p| = i}

.

s

b a

c

35

1-23

s

b a

c

35

1-23

P(s, b) = {(s, a, b), (s, a, c, b)}

b ∈ L2, δ(s, b) = 4

図: Li の例


V =∪

1≤i≤|V|−1





0 1

3 2

3

1

1 1

−1










記号の導入



Li =

{v


|p| = i}

.

s

b a

c

35

1-23

s

b a

c

35

1-23

P(s, b) = {(s, a, b), (s, a, c, b)}

b ∈ L2, δ(s, b) = 4

図: Li の例


V =∪

1≤i≤|V|−1





0 1

3 2

3

1

1 1

−1










記号の導入



Li =

{v


|p| = i}

.

s

b a

c

35

1-23

s

b a

c

35

1-23

P(s, b) = {(s, a, b), (s, a, c, b)}

b ∈ L2, δ(s, b) = 4

図: Li の例


V =∪

1≤i≤|V|−1





0 1

3 2

3

1

1 1

−1










記号の導入



Li =

{v


|p| = i}

.

s

b a

c

35

1-23

s

b a

c

35

1-23

P(s, b) = {(s, a, b), (s, a, c, b)}

b ∈ L2, δ(s, b) = 4

図: Li の例


V =∪

1≤i≤|V|−1





0 1

2 2

3

1

1 1

−1










記号の導入



Li =

{v


|p| = i}

.

s

b a

c

35

1-23

s

b a

c

35

1-23

P(s, b) = {(s, a, b), (s, a, c, b)}

b ∈ L2, δ(s, b) = 4

図: Li の例


V =∪

1≤i≤|V|−1





0 1

2 2

3

1

1 1

−1










記号の導入



Li =

{v


|p| = i}

.

s

b a

c

35

1-23

s

b a

c

35

1-23

P(s, b) = {(s, a, b), (s, a, c, b)}

b ∈ L2, δ(s, b) = 4

図: Li の例


V =∪

1≤i≤|V|−1





0 1

2 2

3

1

1 1

−1










記号の導入



Li =

{v


|p| = i}

.

s

b a

c

35

1-23

s

b a

c

35

1-23

P(s, b) = {(s, a, b), (s, a, c, b)}

b ∈ L2, δ(s, b) = 4

図: Li の例


V =∪

1≤i≤|V|−1





0 1

2 2

3

1

1 1

−1










記号の導入



Li =

{v


|p| = i}

.

s

b a

c

35

1-23

s

b a

c

35

1-23

P(s, b) = {(s, a, b), (s, a, c, b)}

b ∈ L2, δ(s, b) = 4

図: Li の例


V =∪

1≤i≤|V|−1





0 1

2 1

3

1

1 1

−1










記号の導入



Li =

{v


|p| = i}

.

s

b a

c

35

1-23

s

b a

c

35

1-23

P(s, b) = {(s, a, b), (s, a, c, b)}

b ∈ L2, δ(s, b) = 4

図: Li の例


V =∪

1≤i≤|V|−1





0 1

2 1

3

1

1 1

−1










記号の導入



Li =

{v


|p| = i}

.

s

b a

c

35

1-23

s

b a

c

35

1-23

P(s, b) = {(s, a, b), (s, a, c, b)}

b ∈ L2, δ(s, b) = 4

図: Li の例


V =∪

1≤i≤|V|−1





0 1

2 1

3

1

1 1

−1










記号の導入



Li =

{v


|p| = i}

.

s

b a

c

35

1-23

s

b a

c

35

1-23

P(s, b) = {(s, a, b), (s, a, c, b)}

b ∈ L2, δ(s, b) = 4

図: Li の例


V =∪

1≤i≤|V|−1





0 1

2 1

3

1

1 1

−1










記号の導入



Li =

{v


|p| = i}

.

s

b a

c

35

1-23

s

b a

c

35

1-23

P(s, b) = {(s, a, b), (s, a, c, b)}

b ∈ L2, δ(s, b) = 4

図: Li の例


V =∪

1≤i≤|V|−1





0 1

2 1

3

1

1 1

−1










記号の導入



Li =

{v


|p| = i}

.

s

b a

c

35

1-23

s

b a

c

35

1-23

P(s, b) = {(s, a, b), (s, a, c, b)}

b ∈ L2, δ(s, b) = 4

図: Li の例

(s から到達できる) 負のサイクル有りの時

(辺に関して)for 文を回した時はいつでも,そのサイクルのどこかの辺で更新が行われる.

よって最後の for 文のチェックで,どこかの辺でfor 文内の if 文を通る,すなわち更新が行われる.したがって, false が返される.

a

b c

1

1

-3

どこも更新が無いと仮定すると:

a ≤ c − 3 (c, a) で更新を試したが · · ·b ≤ a + 1 (a, b) で更新を試したが · · ·

+) c ≤ b + 1 (b, c) で更新を試したが · · ·

max{a, b, c} < ∞ に注意

図: 更新が行われることの証明のイメージ


Bellman-Fordアルゴリズムの計算量 (P137)






Bellman-Ford のアルゴリズムでは, (1 から 2 行目)配列 d と配列 π の初期化に O(|V |) 時間必要であり,

(4,5 行目) 2 重の for ループ全体で O(|V ||E|) 時間必要である.

(8 行目) 重みの和が負になる閉路があるかどうかのテストは全体で O(|E|) 時間必要である.

したがって,このアルゴリズムの時間計算量は O(|V ||E|) である.


Documents

グラフアルゴリズム - Gunma Universitykoichi/ALG2/7.2beamer.pdfグラフアルゴリズム 山崎浩一 理工学部電子情報理工学科 アルゴリズムII, Autumn 2015

グラフアルゴリズム - Gunma Universitykoichi/ALG2/7.2beamer.pdfグラフアルゴリズム山崎浩一理工学部電子情報理工学科アルゴリズムII, Autumn 2015