第2回 - Donald Home Page

用語の補足

無向グラフ・有向グラフ
無向グラフの辺:{u,v} = {v,u}
有向グラフの辺: (u,v) ≠ (v,u)
H26 グラフ理論
―第2回―
重み付きグラフの最短経路問題
ループ

単純グラフ・多重グラフ

重みなしグラフ・重み付きグラフ
多重辺
3
1
1
1.2: 道と最短経路問題
重み
2
最短経路の単調性
与えられたグラフで,2頂点を結ぶ最も
短い経路を求める問題
14
42
5
14
28
2
5
9
14
2
3
4
5
1
1
1
1
AからBの最短経路の個数
JR浜松町駅から東京ドーム(水道橋)へ行く
最短(あるいは最も乗り継ぎが少ない)ルートは?
1
営団
地下鉄路線図
1
都営
地下鉄路線図
3
A
B
4
1
グラフの部分構造
グラフの部分構造
グラフ G=(V,E) の頂点と辺を交互に並べた列
P: v1 e1 v2 e2 v3 e3 … vn-1 en-1 vn
を考える.このうち各辺が隣同士と接続しているものを
G の v1-vn歩道と呼ぶ.このとき v1を始点,vnを終点という.
v1
G
v3
e7
v6
v1
e1
e3
e2
e5
•すべての辺が異なる歩道を小道という.
•すべての頂点が異なる小道を道という.
•v1=vnである小道を回路という.
•v1=vnである道を閉路という.
v4
v2
v3
e4 e
6
e7
v5
e8
v6
e1
e3
v2
e2
e5
v4
e4 e
6
v5
e8
回路(小道)
閉路(道)
歩道の例 P: v1 e1 v2 e2 v3 e5 v4 e4 v2 e6 v5 e8 v6
単純グラフの場合:辺を省略して P: v1 v2 v3 v4 v2 v5 v6 と書いてよい.
5
グラフの部分構造
閉路(道)は回路(小道)でもあるが,逆は成り立たないことに注意する
6
道と最短経路問題(重み無し)
•頂点 u-v 間に道が存在するとき,u と v は連結しているという.
•任意の2頂点が連結しているグラフを連結なグラフという.
•一般のグラフは連結なグラフ(連結成分)の集まりである.
•連結成分からある辺 e を取り除くと非連結となるとき,
その辺 e を橋という.
2つの点
を結ぶ最短の道は?
連結成分
e
連結グラフ
非連結グラフ
(もっとも一般的なグラフ)
橋e
7
8
2
道と最短経路問題(重み無し)
重み無し最短経路問題:
任意のグラフ G と2点 x,y ∈ V(G)が与えられたとき,
道 Pn={x, v1,…, vn, y}のうち,最短の Pn を求める問題.
見かけは最短経路
異なる経路の数は,|V(G)=n| とすると 2n に比例する.
最短経路問題では,それらの経路から最短のものを
できるだけ短時間に発見したい.
V(G)
x
どうすれば,効率的に
最短経路を発見できるか?
y
x-y道かどうかを確かめる
(指数的な可能性)
頂点を取り出す
9
グラフの重み

10
ダイクストラ(Dijkstra)のアルゴリズム
アイディア
点 x から n ステップで到達できる点の
集合Vnを求める.n = 0から出発して,
ある n に対して y ∈ Vn になったら終了.
最短経路問題のバリエーション
 重み無しグラフ:すべての辺が単一距離を表す
(あるいは重みがない)問題
未知の経路
x
 重み付きグラフ:各辺には重みがあり,目的地ま
での重みの総和が最も小さい道を求めたい
v への最短路
v
y
x

どちらの場合も効率的に解ける方法がある
v への最短路
x
11
y
E.W. Dijkstra (1930-2002)
1972 A. M. Turing Award
v
y
y への最短路
12
3
初期状態
ダイクストラのアルゴリズム(重みなしの場合)
y
入力:グラフ G=(V,E) と 2頂点 x,y
出力:最短の x-y 道
Step1: x と接続している頂点の集合 X を求める
y ∈ X ならば辺 (x,y) を出力して終了
Step2: まだ訪れていない頂点で,v ∈ X と接続している
頂点の集合を求め,新たに X とする
y ∈ X ならば求めた x-y道を出力して終了
x
Step3: y ∈ X となるまで Step2 を繰り返す
13
14
1ステップで到達可能な点
2ステップで到達可能な点
y
y
x
x
X = {すべての }
15
X = {すべての }
16
4
3ステップで到達可能な点
4ステップで到達可能な点
y
y
x
x
X = {すべての }
X = {すべての }
17
18
5ステップで到達可能な点
6ステップで到達可能な点
y
y
x
x
X = {すべての }
19
X = {すべての }
20
5
7ステップで到達可能な点
8ステップで到達可能な点
y
y
x
x
X = {すべての }
X = {すべての }
21
9ステップで到達可能な点
y
22
x-y道の求め方
x から k ステップで到達可能な2つの頂点 u,vがあり,
u,v から1ステップで同じ頂点 w に到達可能ならば,
どちらか一方の経路を記録していればよい
u
kステップ
1ステップ
w
x
x
v
X = {すべての }
23
kステップ
1ステップ
これ以降のパスはどちらから来ても
同じ距離が保証される
※ このようにすると,逆順の辿り方が
一通りに決まる
24
6
x-y間の最短経路(辺数9)
ダイクストラの方法は,すべての路を調べるやり方
に比べて,はるかに効率的である.グラフの頂点数
が n のとき,この方法では,高々 n2 個の路を調べること
で最短経路を求めることができる(効率的な計算が可能)
y
n2 ≪ 2n
素朴な手法に比べて非常に短時間で
答えが求まる!
x
(例えば n=60 の場合でハノイの塔を例に考えてみよ)
25
26
重み付きグラフの条件
より一般的な場合(重み付きグラフ)
問: これまでは頂点間はすべて同じ距離と仮定した.
一般には距離は異なると考えられるが,この場合は,
どのように最短距離を求めればよいか?

重み付きグラフは距離の公理を満たす.


:三角不等式

v
n
d(u,v)
m
距離の違いを数値の
ラベルで表す
u
27
d(u,w)
d(v,w)
w
28
7
重み付きの場合の難しさ
重みなし
重み付き
2
x
一般の場合の解法
y
x
4
y
8
5
y
最適な辺として
これらを選ぶのは
間違い
a
L1
この辺は調べなくてよい
※ 重みの和の大小関係が
途中で入れ替わらない
2
x
2
3
1
b
図のように y に隣接する頂点が3個の
場合, 重み付きの x から y の最短路は
Min{a+L1,b+L2,c+L3}
で計算できる.
c
a, b, cはyに1ステップで到達可能な
頂点とyの間の辺の重み,Liはそれぞれの
頂点への最短経路の重み
L2
L3
x
この問題は,前の場合と同様
にして効率的に計算可能.
y
※ 途中の逆転がある
29
ダイクストラのアルゴリズム(重み付きの場合)
30
実際の例:重み付きの場合
入力:グラフ G=(V,E) と 2頂点 x,y
出力:最短の x-y 道
Step1: L(x)=0 (x から x 自身へは重み0で移動可能) とし,
2
それ以外の v ∈ V は L(v)=∞ とする
x
Step2: 全体で最小のラベル L(v) を見つけ, v=y ならば終了
Step3: v=y ならば終了, それ以外ならすべての (v,u) に対して,
u ∈ V かつ L(u) > L(v) + w(e) ならば
L(u) := L(v) + w(e) とする
5
∞
1
4
0
∞
∞
9
∞
7
3
7
5
4
3
∞
y
2
∞
最短の経路:重み11
Step4: V:=V-{v} としてStep2へ戻る
31
※ X:= X+Y のような式は,X+Y を計算して X に代入することを表す.
32
8