Document

26章
全点対間最短路(後半)
B4 田中翔
26.3 疎グラフに対するJohnsonの
アルゴリズム
• Johnsonのアルゴリズムは全点対間の最短路をO(𝑉 2 lg 𝑉 +
𝑉𝐸)時間で求める。したがって、疎なグラフに対しては、行列
の反復自乗やFloyd-Warshallのアルゴリズムよりも漸近的に
よい。
• アルゴリズムは、全点対に対する最短路重みの行列を返す
か、入力のグラフが負の重みを含むことを知らせる。Johnson
のアルゴリズムは、DijkstraのアルゴリズムとBellman-Fordの
アルゴリズムをサブルーチンとして用いる。
26.3 疎グラフに対するJohnsonの
アルゴリズム
• Johnsonのアルゴリズムは再重みづけの技法を用いる。
– グラフG=(V,E)の辺の重みwがすべて非負ならば、各頂点を始点として一
度ずつDijkstraのアルゴリズムを実行することによってすべての頂点間の
最短路を求めることができる。
• フィボナッチヒープのプライオリティキューを用いると、この全点対
アルゴリズムの実行時間はO(𝑉 2 lg 𝑉 + 𝑉𝐸)となる。
• Gが負の重みの辺をもつ場合には、単に同じ方法が使えるように
する非負の辺重みの新しい集合を求めればよい。
• 新たな辺重みの集合𝑤は次の2つの性質を満たす。
1.すべての頂点対u,v∈ 𝑉に対して、重み関数wを用いた場合のuから
vへの最短路は、重み関数𝑤を用いた場合の最短路でもある。
2.すべての辺(u,v)に対して、新たな重み𝑤は非負である。
• 𝑤を定めるための前処理はO(VE)時間でできる。
26.3 疎グラフに対するJohnsonの
アルゴリズム
補題26.1(再重みづけは最短路を変えない)
重み関数w:E→Rをもつ重みつき有向グラフG=(V,E)が与えられ
たとき、h:V→Rを頂点に実数を割り当てる任意の関数とする。
各辺(u,v)∈ 𝐸に対して、
𝑤 𝑢, 𝑣 = 𝑤 𝑢, 𝑣 + ℎ 𝑢 − ℎ 𝑣
と定義する。p= 𝑣0 , 𝑣1 , … , 𝑣𝑘 を頂点𝑣0 から𝑣𝑘 への経路としたと
き、w(p)=𝛿(𝑣0 , 𝑣𝑘 )であるための必要十分条件は、𝑤 𝑝 =
𝛿(𝑣0 , 𝑣𝑘 )が成り立つことである。
また、重み関数wを用いたとき、Gが負の重みの閉路を含むた
めの必要十分条件は、重み関数𝑤を用いたときにGが負の重み
の閉路を含むことである。
26.3 疎グラフに対するJohnsonの
アルゴリズム
(証明)
定義より、
𝑘
𝑤 𝑝 =
𝑤 𝑣𝑖−1 , 𝑣𝑖
𝑖=1
𝑘
=
(𝑤 𝑣𝑖−1 , 𝑣𝑖 + ℎ 𝑣𝑖−1 − ℎ 𝑣𝑖 )
𝑖−1
𝑘
=
(𝑤 𝑣𝑖−1 , 𝑣𝑖 + ℎ 𝑣0 − ℎ 𝑣𝑘 )
𝑖−1
= 𝑤 𝑝 + ℎ 𝑣0 − ℎ 𝑣𝑘
26.3 疎グラフに対するJohnsonの
アルゴリズム
(証明続き)
w(p)=𝛿(𝑣0 , 𝑣𝑘 )ならば𝑤 𝑝 = 𝛿 𝑣0 , 𝑣𝑘 を背理法により示す。
𝑤を用いると𝑣0 から𝑣𝑘 に、より短い経路p’が存在するとする。
このとき、 𝑤 p′ < 𝑤(p)なので
𝑤 𝑝′ + ℎ 𝑣0 − ℎ 𝑣𝑘 = 𝑤 p′
< 𝑤 p′
= 𝑤 𝑝 + ℎ 𝑣0 − ℎ 𝑣𝑘
よって、w(p’)<w(p)が成り立つが、これはpがwを用いたときのuからv
への最短路であるという仮定に矛盾。逆の証明も同様。
任意閉路c= 𝑣0 , 𝑣1 , … , 𝑣𝑘 (ただし、𝑣0 = 𝑣𝑘 )を考えると、
𝑤 𝑐 = 𝑤 𝑐 + ℎ 𝑣0 + ℎ 𝑣𝑘
=𝑤 𝑐
したがって、cがwを用いたとき負の重みをもつための必要十分条件
は、𝑤を用いたときcが負の重みをもつことである。
26.3 疎グラフに対するJohnsonの
アルゴリズム
• 再重みづけによる非負の重みの生成
重み関数w:E→Rをもつ重みつき有向グラフG=(V,E)が与えられ
たとき、新たなグラフG’=(V’,E’)を作る。ただし、ある新たな頂点
𝑠 ∉ 𝑉に対してV’=V∪{s}およびE’=E∪{(s,v):v∈V}である。この重み
関数wを拡張して、すべてのv∈Vに対してw(s,v)=0が成り立つよ
うにする。
GとG’は負の重みの閉路をもたないとする。すべての辺v∈ 𝑉に
対して、h(v)=𝛿(𝑠, 𝑣)を定義する。補題25.3より、すべての辺
(u,v)∈ 𝐸に対してh(v)≤h(u)+w(u,v)。したがって、 𝑤 𝑢, 𝑣 =
𝑤 𝑢, 𝑣 + ℎ 𝑢 − ℎ(𝑣) ≥ 0が成り立ち、2番目の性質が成り立
つ。
26.3 疎グラフに対するJohnsonの
アルゴリズム
JOHNSON(G)
1 V[G’]=V[G]∪ {s}および
E[G’]=E[G]∪ { 𝑠, 𝑣 : 𝑣 ∈ 𝑉 𝐺 }であるG’を求める
2 if BELLMAN-FORD(G’,w,s) = FALSE
3
then print “入力のグラフは負の重みの閉路をもつ”
4
else for 各頂点 v∈ 𝑉[𝐺 ′ ]
5
do h(v)をBellman-Fordのアルゴリズムで計算される
𝛿(𝑠, 𝑣)の値に設定
6
for 各辺 (u,v)∈ 𝐸[𝐺 ′ ]
7
do 𝑤 𝑢, 𝑣 ← 𝑤 𝑢, 𝑣 + ℎ 𝑢 − ℎ(𝑣)
8
for 各頂点 u∈ 𝑉[𝐺]
9
do すべてのv∈ 𝑉 𝐺 に対して𝛿 𝑢, 𝑣 を求める
ためにDIJKSTRA(G,𝑤, 𝑢)を実行
10
for 各頂点 v∈ 𝑉[𝐺]
11
do 𝑑𝑢𝑣 ← 𝛿 𝑢, 𝑣 + ℎ 𝑣 − ℎ(𝑢)
12 return D
26.3 疎グラフに対するJohnsonの
アルゴリズム
0
-1
0
0
4
3
8
0
0
2
7
-4
-5
1
0
-4
0
6
0
-5
26.3 疎グラフに対するJohnsonの
アルゴリズム
5
-1
1
0
0
4
13
0
0
2
10
0
0
4
-4
0
2
0
-5
0
26.3 疎グラフに対するJohnsonの
アルゴリズム
2/1
0
4
13
0/0
2
10
0
2/-3
0
0
0/-4
2
2/2
26.3 疎グラフに対するJohnsonの
アルゴリズム
0/0
0
4
13
2/3
2
10
0
0/-4
0
0
2/-1
2
0/1
26.3 疎グラフに対するJohnsonの
アルゴリズム
0/4
0
4
13
2/7
2
10
0
0/0
0
0
2/-3
2
0/5
26.3 疎グラフに対するJohnsonの
アルゴリズム
0/-1
0
4
13
2/2
2
10
0
0/-5
0
0
2/-2
2
0/0
26.3 疎グラフに対するJohnsonの
アルゴリズム
2/5
0
4
13
4/8
2
10
0
2/1
0
0
0/0
2
2/6
Johnsonのアルゴリズムの実行時間は、Dijkstraのアルゴリズムに
おけるプライオリティキューをフィボナッチヒープで実現したとき、
O(𝑉 2 lg𝑉+𝑉𝐸)であり、もっと簡単な二分木ヒープによって実現する
と、O(VElgV)となるが、グラフが疎ならば、これでもまだFloydWarshallのアルゴリズムよりも速い。
26.4 有向グラフにおいて経路問題を
解くための一般的な枠組み
• 閉じた半環の定義
・
閉じた半環とは、システム(S, ⊕,○,
0,1)である。ただし、Sは要素の集合、
・
⊕(総和演算)と○(拡大演算)はS上の二項演算である。また
0と1はSの要素
で、次の8つの性質を満たす。
1.(S, ⊕,0)はモノイドである。
• Sは⊕の下で閉じている：すなわち、すべてのa,b∈ 𝑆に対してa ⊕b∈ 𝑆
• ⊕は結合的である：すなわち、すべてのa,b,c∈ 𝑆に対して
a ⊕(b ⊕c)=(a ⊕b) ⊕c
• 0は⊕に対する恒等元である：すなわち、すべてのa∈ 𝑆に対して
a ⊕ 0= 0 ⊕a=a
・ 1)はモノイドである。
同様に、(S,○,
・ 0 = 0○a=
・
2. 0は零化群である：すなわち、すべてのa∈ 𝑆に対してa○
0
3. ⊕は交換的である。すなわち、すべてのa,b∈ 𝑆に対してa⊕b=b⊕a
26.4 有向グラフにおいて経路問題を
解くための一般的な枠組み
• 閉じた半環の定義
4.⊕はべき等的である：すなわち、すべてのa∈ 𝑆に対してa
⊕a=a
・
・
・
・
・
・
・
5.○は⊕に対して分配的である：すなわち、すべてのa,b,c∈
𝑆に
対してa○(b⊕c)=(a○b)⊕(a○c),(b⊕c)○a=(b○a)⊕(c○a)
6.𝑎1 , 𝑎2 , 𝑎3 …がSの可算系列のとき、𝑎1 ⊕𝑎2 ⊕𝑎3 ⊕…は明確に
定義されており、かつ、Sに含まれる。
7.結合性、可換性およびべき等性は無限の和にも当てはまる
・
8.○は無限和に関して分配的である。：すなわち、
・
・
・
・
a○(𝑏1 ⊕𝑏2 ⊕𝑏・3 ⊕…)=(a○𝑏
・
・
・
1 )⊕(a○𝑏
2 )⊕(a○𝑏
3 )⊕…,
(𝑎1 ⊕𝑎2 ⊕𝑎3 ⊕…)○b=(𝑎1 ○b)⊕ (𝑎2 ○b)⊕ (𝑎3 ○b)⊕…
26.4 有向グラフにおいて経路問題を
解くための一般的な枠組み
• 有向グラフにおける経路の計算
閉じた半環の性質は有向グラフにおける経路の計算と関連付
けることができる。
辺(u,v)のラベルをλ(u,v)で表すとすると、λ(u,v)は(u,v)がグラフG
の辺でないときはふつう0となる。
経路p=〈𝑣1 , 𝑣2 , … 𝑣𝑘 〉のラベルは
・
・
・
λ(p)=λ(𝑣1 , 𝑣2 )○λ(𝑣
2 , 𝑣3 )○…○λ(𝑣
𝑘−1 , 𝑣𝑘 )
・
○における恒等元
1は空の経路の役割を果たす。
26.4 有向グラフにおいて経路問題を
解くための一般的な枠組み
閉じた半環の応用例として辺の重みが負でない最短路を考え
る。λ(i,j)=𝑤𝑖,𝑗 とすると、p=〈𝑣1 , 𝑣2 , … 𝑣𝑘 〉のラベルは
・
・
・
λ(p)=λ(𝑣1 , 𝑣2 )○λ(𝑣
2 , 𝑣3 )○…○λ(𝑣
𝑘−1 , 𝑣𝑘 )
=𝑤𝑣1 ,𝑣2 +𝑤𝑣2 ,𝑣3 +…+𝑤𝑣𝑘−1,𝑣𝑘
=w(p)
経路𝑝1 =〈𝑣1 , 𝑣2 , … 𝑣𝑘 〉と𝑝2 =〈𝑣𝑘 , 𝑣𝑘+1 , … 𝑣𝑙 〉が与えられたとき、
それらの連接は𝑝1 ○ 𝑝2 =〈𝑣1 , 𝑣2 , … 𝑣𝑘 〉であり、そのラベルは
・
λ(𝑝1 ○ 𝑝2 )=λ(𝑝1 )○λ(𝑝
2)
可換でかつ結合的である和の演算子⊕を用いて経路のラベル
の和をとる。すなわち、λ(𝑝1 ) ⊕ λ(𝑝2 )の値は𝑝1 と𝑝2 のラベルの
和を与える。
26.4 有向グラフにおいて経路問題を
解くための一般的な枠組み
• ここでの目標はすべての点対i,j∈ 𝑉に対しiからjまでのすべ
ての経路のラベルの和𝑙𝑖,𝑗 =⊕𝑖→𝑗 λ(p)を求めることである。
• 最短路に対しては和の演算子⊕としてminを用いる。minに
対する恒等元は∞である。
• λ(c)=aの閉路があるとすると、閉路cを無限回たどったときの
和をとったラベルa*に対して次式が成り立つ。
𝑎∗ = min {𝑘𝑎}
0≤𝑘<∞
=0
• 𝑆1 = (𝑅≥0 ∪ ∞ , 𝑚𝑖𝑛, +, ∞, 0)は閉じた半環の一つの例であ
る。
26.4 有向グラフにおいて経路問題を
解くための一般的な枠組み
• 負の重みをもつ辺を許すFloyd-Warshallのアルゴリズムに対
して用いる閉じた半環は𝑆2 = (R ∪
−∞, +∞ , 𝑚𝑖𝑛, +, +∞, 0)である。
• 推移的閉包に対しては、 𝑆3 = ( 0,1 ,∨,∧, 0,1) である。ただし、
(i,j)∈ 𝐸のときはλ(i,j)=1,そうでないときはλ(i,j)=0
26.4 有向グラフにおいて経路問題を
解くための一般的な枠組み
• 有向経路のラベルを求める動的計画法アルゴリズム
𝑙𝑖,𝑗 =⊕𝑖→𝑗 λ(p)を計算したい。
(𝑘)
𝑙𝑖𝑗 =⊕𝑝∈𝑄(𝑘) λ(p)と定義する。
𝑖𝑗
再帰的に、
(𝑘)
𝑘−1
𝑙𝑖𝑗 = 𝑙𝑖𝑗
(𝑘−1)・
(𝑘−1) ∗・
(𝑘−1)
) ○𝑙𝑘𝑗 )
○(𝑙𝑘𝑘
⊕(𝑙𝑖𝑘
と定義する。
この定義の基本は
(0)
𝑙𝑖𝑗 =
である。
𝜆 𝑖, 𝑗
1⊕𝜆 𝑖, 𝑗
𝑖 ≠ 𝑗のとき
𝑖 = 𝑗のとき
26.4 有向グラフにおいて経路問題を
解くための一般的な枠組み
COMPUTE-SUMMARIES(λ,V)
1 n← 𝑉
2 for i ← 1 to n
3
do for j ← 1 to n
4
do if i = j
5
(𝑜)
then 𝑙𝑖𝑗 ← 1⊕λ(i,j)
(𝑜)
6
else 𝑙𝑖𝑗 ← 𝜆(𝑖, 𝑗)
7 for k ← 1 to n
8
do for i ← 1 to n
9
do for j ← 1 to n
10
11 return 𝐿(𝑛)
(𝑘)
𝑘−1
do 𝑙𝑖𝑗 ← 𝑙𝑖𝑗
(𝑘−1)・
⊕(𝑙𝑖𝑘
(𝑘−1) ∗・
(𝑘−1)
) ○ 𝑙𝑘𝑗 )
○(𝑙𝑘𝑘
26.4 有向グラフにおいて経路問題を
解くための一般的な枠組み
・
• このアルゴリズムの実行時間は○、
⊕、および*を計算する
時間に依存する。𝑇○・,𝑇⊕ ,𝑇∗ でこれらの時間を表すことにする
と、COMPUTE-SUMMARIESの実行時間はΘ(𝑛3 (𝑇○・+𝑇⊕ +𝑇∗ ))であ
る。よって、これら3つの操作がO(1)でできるなら、Θ(𝑛3 )であ
る。

Download Report