講義「アルゴリズムとデータ構造」

講義「アルゴリズムとデータ構造」

第１４回 グラフとネットワークのアルゴリズム(3)

大学院情報科学研究科 情報理工学専攻 情報知識ネットワーク研究室

喜田拓也

2019/5/21 講義資料

今日の内容

最小全域木を求めるクラスカルのアルゴリズム

（おさらい）

最小全域木を求めるプリムのアルゴリズム プリムのアルゴリズムの考え方

時間計算量が O 𝑚𝑚 log 𝑛𝑛 であることの証明 最短路問題について

最短路と最短路木

ダイクストラのアルゴリズム

ダイクストラ・アルゴリズムの直観的理解

ネットワーク 𝐺𝐺 の最小全域木 （おさらい）

定義：

グラフ 𝐺𝐺𝐺 はネットワーク（重み付きグラフ） 𝐺𝐺 = (𝑉𝑉, 𝐸𝐸) の 最小全域木（最小スパニング木）である

𝐺𝐺𝐺 は 𝐺𝐺 の全域木で含まれる辺の重みの総和が最小のもの ⇕

𝐺𝐺 の最小スパニング木

3 4

2 5 1

2 7

ネットワーク 𝐺𝐺

4 2 1

2

応用例として，通信網の設計，ガス・水道の配管設計などがある

3

[考え方] 解 𝑇𝑇 を空集合から始めて，重みが小さい辺から選択し，

現在の解 𝑇𝑇 に加えていく．ただし，選択することにより閉路ができる 場合は選択しない．

クラスカルのアルゴリズム （おさらい）

クラスカルのアルゴリズムの解 𝑇𝑇 がもつ性質

• 𝑇𝑇 は閉路を含まない

• 𝑇𝑇 は，森になっている（必ずしも連結しているとは限らない）

※ グラフ 𝐺𝐺 が森 ⇔ 𝐺𝐺 は閉路のないグラフ

3 4

2 5 1

2 7

3 4

2 5 1

2 7

3 4

2 5 1

2 7

3 4

2 5 1

2 7

3 4

2 5 1

2 7 _{閉路ができる！}

最小全域木を求めるプリムのアルゴリズム

5

[考え方] 解候補 𝑉𝑉 _𝑇𝑇 , 𝑇𝑇 をある頂点 𝑣𝑣 ₀ のみからなる木（ 𝑣𝑣 ₀ からな る部分グラフに対する最小全域木）から始めて，最小全域木

𝑉𝑉 _𝑇𝑇 , 𝑇𝑇 の範囲を徐々に広げていく．

3 4

2 5 1

2 7

3 4

2 5 1

2 7

3 4

2 5 1

2 7

3 4

2 5 1

2 7

最小全域木が求まっている範囲 𝑉𝑉

, 𝑇𝑇 拡張候補辺（赤い辺）

𝑉𝑉

に属する頂点との間に辺がある

𝑉𝑉 − 𝑉𝑉

に属する頂点（青い頂点）

拡張候補辺を選んだとき 𝑉𝑉

に追加される

3 4

2 5 1

2 7

𝑣𝑣

拡張候補辺のうち，重みが最小のものを選択 その先の頂点を加えたら，拡張候補辺を更新

𝑣𝑣

𝑣𝑣

𝑣𝑣

プリムのアルゴリズム （疑似コード）

Procedure MST-Prim( 𝐺𝐺 = (𝑉𝑉, 𝐸𝐸) : グラフ , 𝑤𝑤 : 重み , 𝑠𝑠 : 起点 ) 1: 𝑣𝑣 ^∗ ← 𝑠𝑠 ; 𝑇𝑇 ← ∅ ; 𝑉𝑉 _𝑇𝑇 ← {𝑠𝑠} ; 𝑑𝑑 𝑠𝑠 ← 0 ;

2: for all 𝑣𝑣 ∈ 𝑉𝑉 － 𝑉𝑉 _𝑇𝑇 do 𝑑𝑑 𝑣𝑣 = ∞ ; 3: while ( 𝑉𝑉 _𝑇𝑇 ≠ 𝑉𝑉 ) do

4: for each ( 頂点 𝑣𝑣 ^∗ と隣接する頂点 𝑣𝑣 ∈ 𝑉𝑉 − 𝑉𝑉 _𝑇𝑇 ) do 5: if ( 𝑤𝑤 𝑣𝑣 ^∗ , 𝑣𝑣 < 𝑑𝑑 𝑣𝑣 ) then

6: 𝑑𝑑(𝑣𝑣) ← 𝑤𝑤(𝑣𝑣 ^∗ , 𝑣𝑣) , 𝑒𝑒(𝑣𝑣) ← 𝑣𝑣 ^∗ , 𝑣𝑣 ;

7: end if

8: end for

9: 𝑣𝑣 ^∗ ← arg min _{𝑣𝑣∈𝑉𝑉−𝑉𝑉}

𝑇𝑇

𝑑𝑑 𝑣𝑣 ;

10: 𝑉𝑉 _𝑇𝑇 ← 𝑉𝑉 _𝑇𝑇 ∪ 𝑣𝑣 ^∗ , 𝑇𝑇 ← 𝑇𝑇 ∪ 𝑒𝑒 𝑣𝑣 ^∗ ; 11: end while

12: 最小全域木 𝑇𝑇 を出力する ;

𝑒𝑒(𝑣𝑣) は 𝑣𝑣 を端点と

する拡張候補辺

𝑑𝑑 (𝑣𝑣) は 𝑣𝑣 を端点と

する拡張候補辺

の重み

プリムのアルゴリズムの動作例

7

3

2 2 2 3

1 4 1

4 3 1 1 2 3 3

0 𝑣𝑣 ^∗

3 2

∞ ∞

∞

∞ ∞

∞

∞

0

𝑣𝑣 ^∗ 2

2

2

1

∞ ∞ ∞

∞

∞

0

𝑣𝑣 ^∗ 2

2

2

1

3 4

∞ ∞

∞

2 𝑣𝑣 ^∗ 0

2

2 1

3 4

4 ∞

∞

2 𝑣𝑣 ^∗ 0 2

2 1

1 4

3 ∞

∞

𝑣𝑣 ^∗ 0 2

2

2 1

1 4

1 ∞

2 𝑣𝑣 ^∗

0 2 2

2 1

1 4

1 ∞

2

𝑣𝑣 ^∗ 0 2

2

2

1

1 1

1 3 2

𝑣𝑣 ^∗ 0 2

2

2

1

1 1

1 3 2

𝑣𝑣 ^∗ 0 2

2

2

1

1 1

1 3 2

𝑣𝑣

：追加された頂点 赤字：更新された値

：拡張候補辺

：解候補

𝑠𝑠

（証明） 1 行目は定数時間で， 2 行目は明らかに O(𝑛𝑛) 時間かかる．

3 行目の while のチェックは 𝑉𝑉 と 𝑉𝑉 _𝑇𝑇 のサイズ比較で行えるため，毎 回の実行は定数時間である．

4 行目の for each のループは新たな 𝑣𝑣 ^∗ 毎に実行される． 𝑣𝑣 ^∗ は結局 はすべての 𝑣𝑣 ∈ 𝑉𝑉 が一度ずつなるので， for each ループの中身は while ループ全体で 2𝑚𝑚 回実行される． for each ループの中身は数 値比較と代入だけなので毎回の実行は定数時間であり，グラフが 隣接リストで与えられている場合，全体で O(𝑚𝑚) 時間で実行できる．

9 行目の arg min の実行は，単純に行うと 𝑘𝑘 回目のループのとき O 𝑛𝑛 − 𝑘𝑘 時間がかかる．しかし，ヒープを使えば 1 回あたり O(log 𝑛𝑛) 時間でできる． 10 行目は明らかに定数時間でできるので，以上から，

while ループ全体では O(𝑚𝑚 + 𝑛𝑛 log 𝑛𝑛) 時間かかることになる．

グラフの連結性より 𝑚𝑚 ≥ 𝑛𝑛 − 1 なので，よって全体を O 𝑚𝑚 log 𝑛𝑛 時間で抑えることができる． 【証明終わり】

最悪時間計算量が O(𝑚𝑚 log 𝑛𝑛) の証明

札幌から新千歳空港への最安乗り換え？

札幌 新札幌 北広島 恵庭 千歳 南千歳 ^新千歳 _空港

9

※ JR 北海道のウェブサイト， 2019 年 5 月 21 日調べ 快速エアポート（自由席）利用の場合

260 260 260 220 170 310

450 450 360 260 350

640 640 450 400

840 640 590

840 880

1070

最短路とは

定義：

無向ネットワーク 𝐺𝐺 = (𝑉𝑉, 𝐸𝐸) において，頂点 𝑢𝑢 ∈ 𝑉𝑉 から頂点 𝑣𝑣 ∈ 𝑉𝑉 への最短路（ shortest path ）とは， 𝑢𝑢 から 𝑣𝑣 への路（ path ）のうち，

辺の重みの総和が最小のものである．

※ 負の重みを許すか否かで問題の難しさが変わる

本講義では，重みはすべて非負の値をとると仮定する 3

2 2 2 3

1 4 1

4

3 1

1 2 3

𝑢𝑢 3

𝑣𝑣

𝑢𝑢 から 𝑣𝑣 への最短路

最短路木とは

11

定義：

辺の重みが非負である連結な無向ネットワーク 𝐺𝐺 = (𝑉𝑉, 𝐸𝐸) に対し，

グラフ 𝐺𝐺′ は頂点 𝑠𝑠 ∈ 𝑉𝑉 からの最短路木（ shortest path tree ）である 𝐺𝐺′ は 𝑠𝑠 を根とする 𝐺𝐺 の全域木で， 𝑠𝑠 ⇕ から各頂点への路が最短路に なっているもの

3

2 2 2 3

1 4 1

4

3 1

1 2 3

𝑠𝑠 3

𝑠𝑠 を根とする最短路木

Edsger W. Dijkstra

(1930–2002)

オランダ

年チューリング賞

最短路木を求めるダイクストラ アルゴリズム

12

[考え方] 解候補 𝑉𝑉 _𝑇𝑇 , 𝑇𝑇 をある頂点 𝑠𝑠 のみからなる木

（ 𝑠𝑠 からなる部分グラフに対する最短路木）から始めて，

最短路木 𝑉𝑉 _𝑇𝑇 , 𝑇𝑇 の範囲を徐々に広げていく．

3 4

2 5 1

2 7

3 4

2 5

2 7

𝟏𝟏

3 4

2 5 7 𝟏𝟏

𝟐𝟐 𝑠𝑠 = 𝑣𝑣

𝑣𝑣

𝑣𝑣

3 𝟒𝟒

2 𝟏𝟏 5

𝟐𝟐 7

𝑣𝑣

最短路木が求まっている範囲

拡張候補辺（赤い辺）

𝑉𝑉

に属する頂点との間に辺がある

𝑉𝑉 − 𝑉𝑉

に属する頂点（青い頂点）

拡張候補辺を選んだとき 𝑉𝑉

に追加される

拡張候補辺は， 𝑢𝑢 ∈ 𝑉𝑉 _𝑇𝑇 と 𝑣𝑣 ∈ 𝑉𝑉 − 𝑉𝑉 _𝑇𝑇 との間の 辺 𝑒𝑒 = (𝑢𝑢, 𝑣𝑣) のうち， 𝑠𝑠 から 𝑢𝑢 への最短路長 𝑑𝑑(𝑢𝑢)

と 𝑤𝑤(𝑒𝑒) の和が最小のもの

3 𝟒𝟒

𝟔𝟔 𝟏𝟏 5

𝟐𝟐 7

𝑣𝑣

ダイクストラ アルゴリズム （疑似コード）

13

Procedure SPT-Dijkstra( 𝐺𝐺 = (𝑉𝑉, 𝐸𝐸) : グラフ , 𝑤𝑤 : 重み , 𝑠𝑠 : 起点 ) 1: 𝑣𝑣 ^∗ ← 𝑠𝑠 ; 𝑇𝑇 ← ∅ ; 𝑉𝑉 _𝑇𝑇 ← {𝑠𝑠} ; 𝑑𝑑 𝑠𝑠 ← 0 ;

2: for all 𝑣𝑣 ∈ 𝑉𝑉 － 𝑉𝑉 _𝑇𝑇 do 𝑑𝑑 𝑣𝑣 = ∞ ; 3: while ( 𝑉𝑉 _𝑇𝑇 ≠ 𝑉𝑉 ) do

4: for each ( 頂点 𝑣𝑣 ^∗ と隣接する頂点 𝑣𝑣 ∈ 𝑉𝑉 − 𝑉𝑉 _𝑇𝑇 ) do 5: if ( 𝑤𝑤 𝑣𝑣 ^∗ , 𝑣𝑣 + 𝑑𝑑 𝑣𝑣 ^∗ < 𝑑𝑑 𝑣𝑣 ) then

6: 𝑑𝑑 𝑣𝑣 ← 𝑤𝑤 𝑣𝑣 ^∗ , 𝑣𝑣 + 𝑑𝑑 𝑣𝑣 ^∗ , 𝑒𝑒(𝑣𝑣) ← 𝑣𝑣 ^∗ , 𝑣𝑣 ;

7: end if

8: end for

9: 𝑣𝑣 ^∗ ← arg min _{𝑣𝑣∈𝑉𝑉−𝑉𝑉}

𝑇𝑇

𝑑𝑑 𝑣𝑣 ;

10: 𝑉𝑉 _𝑇𝑇 ← 𝑉𝑉 _𝑇𝑇 ∪ 𝑣𝑣 ^∗ , 𝑇𝑇 ← 𝑇𝑇 ∪ 𝑒𝑒 𝑣𝑣 ^∗ ; 11: end while

12: 最短路木 𝑇𝑇 を出力する ;

𝑒𝑒(𝑣𝑣 ) は 𝑣𝑣 を端点と する拡張候補辺 𝑑𝑑 (𝑣𝑣) は 𝑣𝑣 を端点と する拡張候補辺 の重み

Prim のアルゴリズムとの 違いは +𝑑𝑑 𝑣𝑣

だけ！

時間計算量は同じ O 𝑚𝑚 log 𝑛𝑛

ダイクストラ アルゴリズムの動作例

3

2 2 2 3

1 4 1

4 3 1 1 2 3 3

0 𝑣𝑣 ^∗

3 2

∞ ∞

∞

∞ ∞

∞

∞

0

𝑣𝑣 ^∗ 3

2

4

3

∞ ∞ ∞

∞

∞

0 3 𝑣𝑣 ^∗ 2

4

3

∞

∞

7 ∞

∞

0 3 2

4 3

6 7

7 ∞

∞ 𝑣𝑣 ^∗

2 𝑣𝑣 ^∗ 0 3

4 3

5 7

7 ∞

∞

𝑣𝑣 ^∗ 0 3

2

4 3

5 7

6 ∞

7 𝑣𝑣 ^∗

0 3 2

4 3

5 7

6 ∞

7

𝑣𝑣 ^∗ 0 3

2

4

3

5 7

6 10 7

𝑣𝑣 ^∗ 0 3

2

4

3

5 7

6 10 7 𝑠𝑠

𝑣𝑣 ^∗ 2

0 3 2

4

3

5 7

6 10 7

𝑣𝑣

：追加された頂点 赤字：更新された値

：拡張候補辺

：解候補

ダイクストラ アルゴリズムの直観的理解

15

3

2 2 2 3

1 4 1

4

3 1

1 2 3

𝑠𝑠 3

𝑠𝑠

辺を細かく分けて，すべての辺の重みが等しく（ 1 に）なるようにする 起点 𝑠𝑠 から幅優先探索を行い，到達した順に頂点を解に加える

1 2 3 5 6 7

8 9

10

4

探索の深さ

最短路に関する発展的な話題

辺の重みが非負整数の場合は平均時 O(𝑚𝑚) まで改善で きる（ただし，ランダムアルゴリズムによる）

[U. Meyar, Single-source shortest-paths on arbitrary directed graphs in linear average- case time, in ACM-SIAM Symposium. Discrete Algorithms, 2001, pp. 797-806.]

ベルマン - フォード アルゴリズム（ Bellman-Ford algorithm ） は正負の重みを扱えるが，最悪時計算量は O(𝑚𝑚𝑛𝑛)

与えられたグラフについて，すべての 2 頂点間の距離を

求めるワーシャル - フロイド アルゴリズム（ Warshall-Floyd

algorithm ）の最悪時間計算量は O(𝑛𝑛 ³ )

札幌から新千歳空港への最安乗り換え！

札幌 新札幌 北広島 ^{260 450} 恵庭 ⁶⁴⁰ 千歳 ⁸¹⁰ 南千歳 ^{840 新千歳} _空港 ¹⁰⁴⁰

17

※ JR 北海道のウェブサイト， 2019 年 5 月 21 日調べ 快速エアポート（自由席）利用の場合

260 260 260 220 170 310

450 450 360 260 350

640 640 450 400

840 640 590

840 880

1070