V - 京都大学

第２５章単一始点最短路
２５．０はじめ
２５．１最短路と緩和法
２５．２ダイクストラのアルゴリズム
２５．０はじめ
• 最短路とは
– 京都の地図が与えられていて、隣接する各交差点の
距離がマークされていいるとき、「吉田寮」から「京都
大学１０号館」までの最短路を求める
– Solve：始点から目的地までのすべての経路を列挙し
て、各経路の距離を合計して最短路を選択する
– 本章ではこのような問題を効率の良く解く方法につい
て述べる
「吉田寮」から「京都大学１０号館」までの最短路
２５．０はじめ
• 最短路とは
辺を実数値の重みに写象する重み関数𝜔：𝐸 → 𝑅
によって重みが付けられた有向グラフG = (𝑉, 𝐸)が
与えられる。経路p =< 𝑣0 , 𝑣1 , … , 𝑣𝑘 >の重みは：
𝑘
𝜔 𝑝 =
𝜔(𝑣𝑖−1 , 𝑣𝑖 )
𝑖=1
e.g.
𝜔 0 → 3 → 2 = 50
２５．０はじめ
𝜇から𝜐への最短路の重みは：
min{ω(p): μ~v}, 経路が存在
𝛿 𝜇, 𝜈 =
∞ , それ以外の時
e.g.
𝛿 0,2 = min 𝜔 0 → 3 → 2 = 50, 𝜔 0 → 1 → 2 = 60
𝛿 0,2 = 0 → 3 → 2
𝛿 2,0 = ∞
２５．０はじめ
• 単一始点最短路
– 与えられた始点から各頂点までの最短路を求める
• 単一目的地最短路
– すべての頂点から与えられた目的地までの最短路を
求める
• 単一点対最短路
– ２つ頂点間の最短路を求める
• 全点対間最短路
– すべての頂点対について、最短路を求める
２５．０はじめ
• 負の重みを持つ辺
– 始点ｓから到達可能な負の重みの閉路があれば、最短路
の重みは明確に定義できない
– Dijkstraアルゴリズムは、与えられた辺がすべて非負であ
ると仮定する
– Bellman-Fordのアルゴリズムはグラフの負の重みでも使
える。負の重みの閉路が存在すれば、検出できる。
5
A
10
B
C
5
5
D
-20
E
10
２５．０はじめ
• 最短路の表現
– 先行点
𝑣の先行点はグラフには𝑣の直前の頂点である。なければ、NILで表
す。𝜋 𝑣 = 𝑣0 or NIL
– 先行点部分グラフ
先行点がNILでないGの頂点の集合に始点sを加えたものである。
𝑉𝜋 = 𝑣 ∈ 𝑉: 𝜋 𝑣 ≠ 𝑁𝐼𝐿 ∪ {𝑠}
– 最短路木
始点sを根とする、sから各頂点までの最短経路で
構成する木である
２５．０はじめ
• 最短路と最短路木が必ずしも一つではない
２５．１最短路と緩和法
• 最短路の部分構造の最適性
補題25.1：最短路の部分経路は最短路である
証明：（背理法）
最短路𝑤 𝑝 = 𝑤 𝑝1𝑖 + 𝑤 𝑝𝑖𝑗 + 𝑤 𝑝𝑗𝑘
′
′
ここで𝑤 𝑝𝑖𝑗
< 𝑤 𝑝𝑖𝑗 の経路𝑝𝑖𝑗
が存在すると仮定
′
すると、その重み𝑤 𝑝1𝑖 + 𝑤 𝑝𝑖𝑗
+ 𝑤 𝑝𝑗𝑘 は
𝑤 𝑝 より小さい、これは𝑤 𝑝 が最短路という前提
に矛盾する。 ∎
２５．１最短路と緩和法
• 系25.2
– 始点sから頂点ｖへの最短路がある頂点uと経路𝑝′ に対し
𝑝′
てｓ→u→vに分割できるものと仮定する。このとき、ｓからｖ
への最短路の重みは𝛿 𝑠, 𝑣 = 𝛿 𝑠, 𝑢 + 𝜔(𝑢, 𝑣)
証明
補題25.1により、部分経路𝑝′ は最短路である。したがって、
𝛿 𝑠, 𝑣
=𝜔 𝑝
= 𝜔 𝑝′ + 𝜔(𝑢, 𝑣)
= 𝛿 𝑠, 𝑢 + 𝜔 𝑢, 𝑣
■
２５．１最短路と緩和法
• 補題25.3
– 辺(𝑢, 𝑣)に対して𝛿 𝑠, 𝑣 ≤ 𝛿 𝑠, 𝑢 + 𝑤(𝑢, 𝑣)が成
り立つ。
証明
始点ｓから頂点ｖまでの最短路はｓからｖへ他のど
の経路よりも大きな重みをもつことはない。特に、
経路ｐが始点ｓから頂点uへの最短路をたどり、そ
のあと辺(𝑢, 𝑣)を通る特定の経路より大きな重みを
持つことはない。■
２５．１最短路と緩和法
• 緩和法
– 初期化：ｓから各頂点まで最短路を初期化する
INITIALIZE-SINGLE-SOURCE(G, s)
1 for each vertex v ∈ V[G]
2
do d[v] ← ∞
3
π[v] ← NIL
4 d[s] ← 0
Gはグラフ
sは始点
d[v] は今まで見つけたｓからｖまでの最短路の重み
π[v]はまで見つけた最短路には、ｖの直前の頂点
２５．１最短路と緩和法
• 緩和法
– 緩和操作：もしｓからｖまでもっと短い経路があれば、
d[v]とπ[v]を更新する（補題25.3）
RELAX(u, v, w)
1 if d[v] > d[u] + w(u, v)
2
then d[v] ← d[u] + w(u, v)
3
π[v] ← u
Gはグラフ sは始点
d[v] は今まで見つけたｓからｖまでの最短路の重み
π[v]はまで見つけた最短路には、ｖの直前の頂点
２５．２ダイクストラのアルゴリズム
• アイデア
– 「最短路の部分経路は最短路である」
– 始点ｓから各頂点への重みを∞で初期化して、各
頂点を対象に重みの緩和操作RELAXを繰り返す
– 貪欲法的な手法
– 優先度付きキュー
２５．２ダイクストラのアルゴリズム
• コード
DIJKSTRA(G, w, s)
1 INITIALIZE-SINGLE-SOURCE(G, s)
2 S←Ø
▹Sを空集合として初期化
3
Q ← V[G]
▹Qを初期化、 |V|回のQ-INSERT（）操作
4
while Q ≠ Ø
▹|V|回の繰り返し
5
do u ← EXTRACT-MIN(Q) ▹重みの最も小さいもの返す
6
S ← S ∪{u}
▹最短路の頂点集合を更新する
7
for each vertex v ∈ Adj[u]
▹
8
do RELAX(u, v, w)
▹ d[v]とπ[v]を更新する
Sは見つけた最短路の頂点集合
Qは優先度付きキュー、QのKEYは頂点ｖへの最短経路d[v]
EXTRACT-MIN(Q)はキューの最優先のものを返す
２５．２ダイクストラのアルゴリズム
• 直感的例
– http://www.ntnoi.cn/FLASH/arithmetic/2010-0517/23.html
– http://www.cs.usfca.edu/~galles/visualization/Dijk
stra.html
２５．２ダイクストラのアルゴリズム
• 計算量
DIJKSTRA(G, w, s)
1 INITIALIZE-SINGLE-SOURCE(G, s)
2 S←Ø
▹Sを空集合として初期化
3
Q ← V[G]
▹Qを初期化、 |V|回のQ-INSERT（）操作
4
while Q ≠ Ø
|V| Times
5
do u ← EXTRACT-MIN(Q) ▹重みの最も小さいもの返す
6
S ← S ∪{u}
▹最短路の頂点集合を更新する
7
for each vertex v ∈ Adj[u]
8
do RELAX(u, v, w)
▹ d[v]とπ[v]を更新するQ-DECREASEKY
計算量は|V|*Q-INSERT+ |V|* EXTRACT-MINs +|E|* Q-DECREASEKY
各頂点ｖが集合Sに一度だけ挿入されるから、隣接リストの各辺は７－８行のFor
ループにおいてアルゴリズムの実行中一度だけ調べられる。隣接リストの辺数
は|E|であるから…
２５．２ダイクストラのアルゴリズム
• 計算量
|V|*Q-INSERT+ |V|* EXTRACT-MIN +|E|* Q-DECREASEKY
実装
Q-INSERT
リスト
O(1)
O(V)
O(1)
𝑂(𝑉 2 + 𝐸)
２ーヒープ
𝑂(𝑙𝑔𝑉)
𝑂(𝑙𝑔𝑉)
𝑂(𝑙𝑔𝑉)
O( 𝐸 + 𝑉 𝑙𝑔𝑉)
フィボナッ
チ・ヒープ
Q-INSERT+
DECREASE＝O(1)
𝑂(𝑙𝑔𝑉)
--
O(𝐸 + 𝑉𝑙𝑔𝑉)
Q-EXTRACT
QDECREASE
合計
２５．２ダイクストラのアルゴリズム
• PrimとDijkstraの違いところ
– Prim：幅優先探索と最小全域木を求める
Dijｋstra：単一始点の最短路
– Prim：アルゴリズムが行なっているノートにとってコストが
最も小さいノートを探す；
Dijkstra：アルゴリズムが行なっていた
ノーたの集合にとって、コストが最も
小さいノートを探す。
• PrimとDijkstraの違いところ

Download Report