グラフ・ネットワークの基礎用語

ネットワーク理論
Text. Part 3 pp. 57-104
• 最短路問題 pp.58-84
• Ford法,双対問題とポテンシャル，
Bellman方程式とBellman-Ford法
• 負の費用をもつ閉路がある場合，閉
路を含まない場合
• 最大流問題 pp.85-94
• 最小費用流問題 pp.95-104
1
大名の例題
10
s
始点
飛脚に払う費用
（単位は両）
1
1
3 2
5
2
t
終点
6
2
3
2
最短路問題（定義）
V
 枝集合 E
 点集合
c は枝集合Ｅから
非負の実数全体への写像
G=(V,E)
 枝の費用 c: E → R+
 有向グラフ
 目的：
点とそれに接続する
枝が交互に並んだもの
始点sから終点tまでの最小費用のパス
最短路
3
Ford法（アイディア）
費用=10（両）
富士山
氷の価格=0（両）
宿場１
氷の価格=9（両）
氷の価格=10（両）
氷を運びますか？
氷の価格=11（両）
4
アイディアの形式化
小売価格＝ポテンシャル
c
費用=
点v
y
氷の価格= v（両）
氷を運びますか？
ywがyv＋cvw以上なら
飛脚は氷を運ぶ！
vw
点w
氷の価格=
yw（両）
点のポテンシャル
y : V→ R
y は点集合 V から
実数全体への写像
5
「小売価格の見直し」操作
費用=10（両）
宿場１
富士山
氷の価格=0（両）
小売価格が
適正でない！
氷の価格=13（両）
小
見売
直価
し格
の
氷の価格=10（両）
6
Ford法（飛脚組合バージョン）
1.
2.
3.
富士山の氷の価格=0；他の宿場町の氷の価
格＝∞
while 小売価格が適正でなければ．．． do
（wにおける）価格が適正でない枝 vw に対して
「小売価格の見直し」
7
解いてみよう！（１）
10
s
1
1
3 2
5
2
t
6
2
3
8
解いてみよう！(２）
∞
0
1
10
s
1
∞
t
3 2
6
2
3∞
5
∞
2
9
解いてみよう！(３）
∞
0
1
10
s
1
∞
t
価格が適正でない
3 2
6
2
3∞
5
∞→5
2
10
解いてみよう！(４）
∞→10
0
10
1
1
∞
t
価格が適正でない
s
5
5
3 2
6
2
3∞
2
11
解いてみよう！(５）
10→8
0
1
10
1
∞
t
価格が適正でない
s
5
5
3 2
6
2
3∞
2
12
解いてみよう！(６）
8
0
1
10
1
∞
t
価格が適正でない
s
3 2
6
∞→7
5
5
2
2
3
13
解いてみよう！(７）
8
0
1
10
s
1
∞→13
3 2
5
t
6
価格が適正でない
5
2
2
37
14
解いてみよう！(８）
8
0
1
10
s
1
13→9
3 2
t
6
価格が適正でない
5
5
2
2
37
15
解いてみよう！(９）
8
0
1
10
s
3 2
5
5
2
1
全ての価格が
適正になった
2
9
t
6
37
16
ポテンシャルの実行不能，実行可能
 小売価格＝ポテンシャル
 ポテンシャルが実行不能
（小売価格が適正でない）
yw  yv  cvw
 ポテンシャルが実行可能
（小売価格が適正）
yw  yv  cvw
17
Ford法
1.
2.
3.
集合の差演
算
ys:=0， yv :＝∞, v V \ s
While ポテンシャル yが実行不能 do
yw>yv+cvwを満たす枝を見つけて
yw:=yv+cvw
18
双対問題とポテンシャル
-まずは線形計画として定式化変数 xvw: 最短路（最適パス）が枝vwを使う
なら１，それ以外なら0
 例：始点 s に対して，
xs1=0, xs2=1 （８ページ目のスライド参照）

xがパスを表すためには．．．
始点 s から飛脚が１人出ていく！
xs1+xs2=1
19
線形計画として定式化２
xがパスを表すためには．．．
点1に飛脚が入ってきたら出ていかなければ
ならない！
xs1+x21 -x12-x1t =0
 点2に飛脚が入ってきたら出ていかなければ
ならない！
xs2+x12 –x21-x23 =0
 点3に飛脚が入ってきたら出ていかなければ
ならない！
x23-x3t =0
 終点tには飛脚が入ってくる！
x1t+x3t =１
20

線形計画として定式化３
 パスに含まれている枝の費用の合計は最小化
最小化10xs1+5xs2+2x12+x1t+3x21+2x23+6x3t
条件 -xs1- xs2
=-1
xs1
- x12-x1t+ x21
=0
xs2+ x12
- x21- x23
=0
x23- x3t =0
x1t
+ x3t =1
xs1, xs 2 , x12 , x1t , x21 , x23 , x3t  0
21
双対問題を作ってみよう！
 絶対に失敗しない方法
(Lagrange緩和
を用いる！）
まず，主問題のそれぞれの制約式に対応する双対変数を用意
22
双対問題を作ってみよう！
最小化10xs1+5xs2+2x12+x1t+3x21+2x23+6x3t
条件 -xs1- xs2
=-1
xs1
- x12-x1t+ x21
=0
xs2+ x12
- x21- x23
=0
x23- x3t =0
x1t
+ x3t =1
(xs1+xs2-1)×ys
(-xs1+x12+x1t-x21)×y1
(-xs2-x12+x21+x23)×y2
任意の実数
(-x23+x3t)×y3
（負でも良い）
=0
(-x1t-x3t+1)×yt
×ys
×y1
×y2
×y3
×yt
23
双対問題を作ってみよう！
最小化
10xs1+5xs2+2x12+x1t+3x21+2x23+6x3t
+(xs1+xs2-1)ys+(-xs1+x12+x1t-x21)y1
+(-xs2-x12+x
+x23)y2+(-x23+x3t)y3
=0 21
任意の実数
+(-x1t-x3t+1)yt
条件
この部分は0
主問題と同じ
24
双対問題を作ってみよう！
目的関数をyについてまとめる
最小化
yt-ys
+(10+ys-y1)xs1+(5+ys-y2)xs2+(2+y1-y2)x12
+(1+y1-yt)x1t+(3+y2-y1)x21
+(2+y2-y3)x23+(6+y3-yt)x3t
条件
主問題と同じ
25
双対問題を作ってみよう！
目的関数に加えた制約を全て緩和
最小化
下界を与える
yt-ys+(10+ys-y1)xs1+(5+ys-y2)xs2+(2+y1-y2)x12
+(1+y1-yt)x1t+(3+y2-y1)x21+(2+y2-y3)x23+(6+y3-yt)x3t
条件
xは0以上
0以上でないと
最小化
発散してしまう
最大化
最適値
下界（目的関数に加えた項の
合計は０，式を緩和したので）
26
双対問題
双対問題
最大化
yt-ys
条件
y1  y s  10
ポテンシャルが実
行可能である条件
y2  y s  5
小売価格が適正
y2  y1  2
yt  y1  1
y1  y2  3
y3  y 2  2
yt  y3  6
27
双対問題の意味合いを考えてみよう
（ポテンシャルと双対変数の関係）
 双対変数yは宿場町での氷の小売価格
（ポテンシャル）を表す．
 双対問題の目的関数は，江戸と富士山の
小売の価格（ポテンシャル）の差の最大
化を表す．
 双対問題の制約式は，小売価格が適正
（ポテンシャルが実行可能）であること
を表す．
28
Bellman方程式とBellman-Ford法
-双対問題を眺めてみよう！y1  ys  10
y1  y2  3
よりy1=min{ys+10,y2+3}である．
同様に
y2=min{ys+5,y1+2},
y3=min{y2+2},
yt=min{y1+1,y3+6}
29
Bellman方程式
つまり次式を満たすyを求めれば良い．
yw  min yv  cvw w V \ s
v:vwE
ys  0
Bellman方程式
30
Bellman方程式を解こう１
ys=0（富士山sの小売価格は０）
y1=min{ys+10,y2+3}
y1=min{10,y2+3}
y2=min{ys+5,y1+2}
y2=min{5,y1+2}
y3=min{y2+2}
y3=y2+2
yt=min{y1+1,y3+6}
yt=min{y1+1,y3+6}
31
Bellman方程式を解こう２
y1=min{10,y2+3}を y2=min{5,y1+2} に代入
y2=min{5,min{10,y2+3}+2}
整理して
y2=min{5,min{12,y2+5}}
もっと整理して
y2=min{5,12,y2+5}；よって y2 =5
32
Bellman方程式を解こう３
y2 =5 がわかったので．．．
y1=min{10,y2+3}より y1=min{10,5+3} =8
y3=y2+2 より y3=5+2=7
yt=min{y1+1,y3+6}より yt= min{8+1,7+6}=9
より系統的な方法はないものか？
（手計算でなくコンピュータでもできるように！）
33
Bellman方程式（修正版）
yv(k)=始点sから，たかだかk本の枝を経由し，
点vに至る最適パスの費用
点wにk+1本の枝を経由してくるときの費用
yw k  1  min yv k   cvw , yw k  w V \ s
v:vwE
点vにk本の枝を経由してくるときの
点wにk本の枝を経由
費用にvからwへ移動の費用を加えたものしてくるときの費用
34
Bellman方程式（修正版）をもと
にしたFord法
-Bellman-Ford法Bellman-Ford法を言葉で書くと．．．
k＝０のときは簡単！
ys(0)=0（始点 s までは枝 0 本で費用０）
yv(0)=∞（s以外の点vには，枝 0 本では行けない）
これを初期条件として．．．
k=1,2,3,4（点の数から１を減じた回数だけ；なぜか？）
の順にy(k) を計算する．
35
Bellman-Ford法の適用例
表の値はyv(k)
点 k=0
k=1
k=2
k=3
k=4
s
0
0
0
0
0
1
∞
10
8
8
8
2
∞
5
5
5
5
3
∞
∞
7
7
7
t
∞
∞
11
9
9
最適値
36
Bellman-Ford法
ys(0):=0, yv(0):=∞, v V \ s
for k=0 to n-1 do
yw(k+1):=yw(k) ,∀w ∈V
for all vw  E do
if yv(k)+cvw<yw(k) then
yw(k+1):=yv(k)+cvw
37
Bellman-Ford法の適用例
最適パスを記憶する場合
sからきたことを表
pr k=2 pr k=3す pr k=4
点
k=0 pr k=1
s
0
0
1
∞
10
s 8
2
8
2
8
2
2
∞
5
s 5
s
5
s
5
s
3
∞
∞
7
2
7
2
7
2
t
∞
∞
11
1
9
1
9
1
0
0
pr
0
表の値はyv(k)と直前の点pr（Previousの略）
38
Bellman-Ford法の適用例
点
k=0
k=1
pr
s
0
0
1
∞
2
∞
3
∞
10
s
5
s
∞
t
∞
∞
k=2 k=3 k=4 pr
pr sからきたことを表
pr
0
0
す 0
8
2
5
s
7
2
11
1
8
2
5
s
7
2
9
1
8
2
5
s
7
2
9
1
最適値
39
最短路木
（最適パスの情報を含んだ木）
Bellman-Ford法の表を後からたどることにより，
最短路木を作成
1
t
2
3
s
40
演習問題１
1. Aから各点への最短路をFord法で求めてみよう．
2. Aから各点への最短路をBellman-Ford法で求めてみよう．
A
B
4
E
5
4
9
3
C
F
3
10
注：無向グラフなので
A->B,B->Ａの両方向に
枝がある有向グラフと
みなして解くこと！
3
D
4
41
演習問題２
下のネットワークにおいて，sからtへの最短路を
Bellman-Ford法で求めることができるかな？
（オプション課題）
10
s
1
3 2
5
2
1
-5
2
t
6
3
42
ネットワーク理論
Text. Part 3 pp. 57-104
• 最短路問題 pp.58-84
• Ford法,双対問題とポテンシャル，
Bellman方程式とBemmlan-Ford法
• 負の費用をもつ閉路がある場合，閉
路を含まない場合
• 最大流問題 pp.85-94
• 最小費用流問題 pp.95-104
43
大名の例題
10
始点
s
飛脚に払う費用
（単位は両）
1
3 2
5
2
1
-5
2
t
終点
6
3
Ford法を適用してみよう
44
Ford法の適用
∞
1
∞
1
t
10
0
s
3
5
-5
2
2
∞
2
6
3
∞
45
Ford法の適用
∞→10
1
∞
1
t
10
0
s
3
5
-5
2
2
∞
2
6
3
∞
46
Ford法の適用
10
1
∞
1
t
10
0
s
3
5
-5
2
2
∞→5
2
6
3
∞
47
Ford法の適用
10
1
∞
1
t
10
0
s
3
5
-5
2
2
5
2
6
3
∞→7
48
Ford法の適用
10→2
1
∞
1
t
10
0
s
3
5
-5
2
2
5
2
6
3
7
49
Ford法の適用
10→2→1→
1
∞
1
t
10
0
s
3
5
終わらない！
-5
2
2
2
6
3
5→4→3→
7→6→5→
合計費用が負の閉路
（＝負の閉路）
50
最短路問題
（枝の費用が負を許す場合）
（下線を引いた部分が改訂箇所）
V
 枝集合 E
 点集合
G=(V,E)
 枝の費用 c: E → R
 有向グラフ
（Rは実数全体の集合；負でも良い！）
 目的：
始点sから終点tまでの最小費用のパス
あるいは負の閉路を見つける
51
Ford法は失敗した！
Bellman-Ford法はどうだろう？
（復習）
yv(k)=始点sから，たかだかk本の枝を経由し，
点vに至る最適パスの費用
Bellman-Ford法を言葉で書くと．．．
k＝０のときを初期条件として．．．
k=1,2,3,4
（点の数は5個;最適パスの枝は最大でも4本だから！）
の順にyv(k)を計算する．
52
Bellman-Ford法のちょっとし
た変形（アイディア）
 最適パスは枝をたかだか４本使う．
 ５本使ったときに，最適パスの費用
yv(k)が（４本使ったときより）小さく
なったら，負の閉路がある！
53
改訂したBellman-Ford法
（負の費用をもつ枝をもつ
最短路問題に対するアルゴリズム）
改訂したBellman-Ford法
k＝０のときを初期条件として，
k=1,2,3,4,5 まで
yv(k)を計算し，yv(4) > yv(5)になる点 v がある
なら「負の閉路がある」といって終了
それ以外なら， yｔ(4)が最適パスの費用
54
Bellman-Ford法（擬似コード）
（下線を引いたのが改訂箇所）
ys(0):=0, yv(0):=∞, v V \ s
pred(v):=empty, v  V
for k=0 to n do
yw(k+1):=yw(k) ,∀w ∈V
for all vw  E do
if yv(k)+cvw<yw(k) then
yw(k+1):=yv(k)+cvw
pred(w):=v
55
Bellman-Ford法を適用してみよう
表の値はyv(k)と直前の点pr（Previousの略）
点
k=0 k=1 k=2 k=3 k=4 k=5
pr pr pr pr pr pr
s
0
1
∞
2
∞
3
∞
∞
t
∞
∞
0
0
0
0
0
10
s
5
s
8
2
5
s
7
2
11
1
2
3
5
s
7
2
9
1
2
3
4
1
7
2
3
1
2
3
4
1
6
2
3
1
v=3に対して
yv(4) >yv(5)
56
最短路木の作成
Bellman-Ford法の表を後からたどることにより，
最短路木を作成
点 … k=5 pr
s
… 0
tの直前は1
1
… 2
3
2の直前は1
1の直前は3
2
… 4
1
3
… 6
2
t
… 3
1
1
s
2
t
3
3の直前は2
57
最短路木の作成
Bellman-Ford法の表を後からたどることにより，
最短路木を作成
点 … k=5 pr
1
t
s
2
3
s
… 0
1
負の閉路
発見
… 2
3
2
… 4
1
3
… 6
2
t
… 3
1
58
通貨の変換によって儲けよう
￥
1ドル＝112.44円
×112.44
1円＝0.007689ユーロ
1ユーロ＝1.1567ドル
＄
×0.007689
ユーロ
×1.1567
1×112.44×0.007689×1.1567＝1.000026326772
投資額が大きい機関投資家なら手数料が無視できる
ので，ちょっと儲かる．
59
通貨の変換によって儲けよう
通貨vから通貨wへの変換レートを Rvk,v1 とする．
通貨を点としたグラフで，閉路 v1->v2->…vk->v1で
Rv1,v2× Rv2,v3×‥‥ Rvk-1,vk× Rvk,v1＞1
となるものを求める問題．
枝vw上の費用cvwをcvw=-log Rvwとすると
-(logRv1,v2+logRv2,v3+‥‥+logRvk-1,vk+logRvk,v1)=
-log(Rv1,v2×Rv2,v3×‥‥×Rvk-1,vk×Rvk,v1) < 0
なのでグラフ上で負の閉路を求める問題に帰着される．
61
通貨の変換によって儲けよう
 注意！個人投資家がやっても，手数料
があるので儲からない．
（日本の）銀行だと１＄あたり1円の手数料がかかる．
 一度に変換する額が大きすぎると，為
替レート自身が動いてしまう．
-> 次々回にやる最小費用流を用いて，一度に変換す
る量に制限（容量）をつける．
62
大名の例題
ストライキ
10
始点
s
1
3 2
5
2
1
-5
2
t
終点
6
3
64
大名の例題
（閉路がない場合）
1
1
t
10
s
-5
3
5
2
2
6
3
閉路がなくなったので，枝の費用が負でも
負の閉路ができる心配はない！
65
閉路がないグラフ上の問題を
解くときの基本ツール
-トポロジカル・ソート-
s
2
3
1
t
トポロジカル・ソート
（topological sort;位相の情報を用いた並べ替えの意）
66
並べ替えのアルゴリズム
（ソーティング）（復習？）
 挿入ソート（insertion
sort）
やってみよう！
67
並べ替え(ソーティング)
 問題の入力
– データの個数nおよびデータのキー
A[j](j=1,・・・,n)
 出力
– A[j](j=1,・・・,n)を小さい順に並べた列
挿入ソート
マージソート
クイックソート
ヒープソート
良いアルゴリズム
O(n2)
O(n logn)
O(n2) 平均的にはO(n logn)
O(n logn)
68
挿入ソート(Insertion sort)
1
2
3
jを２からnまで１ずつ増やす
A[1..j-1]まではちゃんと並べられている
A[j]をA[1..j]の中の適切な場所に挿入する
j
A[j]
1
3
2
2
A[j]
2
3
A[j]
2
A[j]
1
3
4
4
1
A[1..1]はOK
4
1
A[1..2]はOK
3
4
1
A[1..3]はOK
2
3
4
A[1..4]はOK
69
挿入ソート(Insertion sort)
「A[j]をA[1..j]の中の適切な場所に挿入する」の詳細化
key =A[j]
i=j-1から1まで，key<A[i]になるまでA[i]を右にずらす
key（A[j])をずらした位置に入れる
keyに一時保存
A[j]
A[j]
2
1
3
4
2
3
2
3
1
A[1..3]はOK
4
4
A[1..4]はOK
70
挿入ソート(Insertion sort)
1
2
3
4
5
jを２からnまで１ずつ増やす
key = A[j]
iをj-1からA[i]>keyまたはi=0になるまで１ずつ減らす
A[i+1]=A[i]
A[i+1] =key
最悪の場合の計算量： O(n2)
n2 回かかる例：
A[j]
5
4
3
2
1
A[j]
1
2
4
3
5
71
トポロジカル・ソート
言葉の準備（復習！覚えているかな？）
入次数：点に入ってくる枝の数
出次数：点から出て行く枝の数
1
t
入次数：0
入次数：2
入次数：1
入次数：3
入次数：1
出次数：2
出次数：0
出次数：2
出次数：1
出次数：2
s
2
3
72
トポロジカル・ソート
While グラフに点がある do
入次数＝０の点を見つける
（必ず一つは見つかる）
その点とその点に入ってくる枝をグラフから消す
点を消した順に左から並べる
やってみよう
73
トポロジカル・ソート2
3
1
t
入次数が0なので
この点と
この点から出る枝を消す
0
s
1
1
2
3
74
トポロジカル・ソート2
3
1
t
0
s
1
1
2
3
75
トポロジカル・ソート2
2
1
t
入次数の変化
する点がある
0
1
2
3
s
76
トポロジカル・ソート2
2
1
t
入次数が0なので
この点と
この点から出る枝を消す
0
1
2
3
s
77
トポロジカル・ソート2
2
1
t
0
1
2
3
s
78
トポロジカル・ソート2
1
1
t
入次数の変化
する点がある
0
3
s
2
79
トポロジカル・ソート2
1
1
t
入次数が0なので
この点と
この点から出る枝を消す
0
3
s
2
80
トポロジカル・ソート2
1
1
t
0
3
s
2
81
トポロジカル・ソート1
0
1
t
入次数の変化
する点がある
s
2
3
82
トポロジカル・ソート1
0
1
t
入次数が0なので
この点と
この点から出る枝を消す
s
2
3
83
トポロジカル・ソート1
0
s
1
2
t
3
84
トポロジカル・ソート1
t
s
2
3
1
85
トポロジカル・ソート
s
2
3
1
t
86
トポロジカル・ソートの擬似コード
点vの入次数をindegree(v)と書く
indegreeの初期設定
1. indegree(v):=0, v  V
2. for all v  V do
3.
for all w : vw  E do
4.
indegree(w):=indegree(w)+1
87
トポロジカル・ソートの擬似コード
入次数が0である点のリストをLISTと書く
LISTの初期設定
1. LIST:=empty
2. for all v  V do
3.
if indegree(v)=0 then
LIST : LIST  v
4.
88
トポロジカル・ソートの擬似コード
トポロジカル・ソート
1.
indegreeの初期設定
2.
LISTの初期設定
3.
while LISTが空でない do
4.
LISTから適当に点vを選択し，vを左詰めで並べる
5.
for all w : vw  E do
6.
indegree(w):=indegree(w)-1
7.
if indegree(w)=0 then
LIST : LIST  v
8.
89
Ford法の高速化（アイデア）
トポロジカル・ソートを用いるとFord法を高速化できる．
なぜか？
トポロジカル・ソートされた順にポテンシャル
を更新すれば，あともどりがなくなる
（つまり，ポテンシャルは１回だけ更新すれば良い）から
やってみよう
90
大名の例題
1
1
t
10
s
-5
3
5
2
2
6
3
トポロジカル・ソートすると
91
Ford法（高速化版）
3
6
0
∞
∞
∞
s
2
3
1
5
2
-5
∞
1
t
10
92
Ford法（高速化版）
3
6
0
∞→5
∞
∞→10
s
2
3
1
5
10
2
-5
∞
1
t
点v（上の場合はs）の走査（scan）
1.
for all w : vw  E do
2.
if yv+cvw<yw then
3.
yw:=yv+cvw
93
Ford法（高速化版）
3
0
5
s
2
5
6
∞→7
2
3
10→8
-5
1
∞
1
t
10
94
Ford法（高速化版）
3
6
0
5
7
s
2
3
5
2
8→2
-5
1
∞→13
1
t
10
95
Ford法（高速化版）
3
6
0
5
7
2
s
2
3
1
5
2
-5
13→3
1
t
10
96
Ford法（高速化版）
最短路が
求まった
3
6
0
5
7
2
s
2
3
1
5
2
-5
3
1
t
10
ちゃんと書くと
97
Ford法（高速化版）
ちゃんと書くと
点vの走査
1.
for all w : vw  E do
2.
if yv+cvw<yw then
3.
yw:=yv+cvw
宿場町vから直接
行ける宿場町の
価格を一度に見直す！
閉路を含まないグラフに対するFord法
1.
グラフをトポロジカル・ソート（その順にv1,v2,…)
2.
ポテンシャルyの初期設定
3.
for i=1 to n do
4.
点viの走査
98
航空機を早く離陸させよう
（閉路なし最短路問題の一例）
13分
15分
25分
27分
22分
飛行機の着陸から離陸まで最低何分かかるかな？
最短路問題に変形してみよう
99
航空機を早く離陸させよう
13分
15分
27分
点ではなく枝に長さを持つ
ネットワークに変形
→閉路のない最短路問題に
25分
22分
ダミーの枝
-15
-27
-13
0
s
-25
-22
t
100
航空機を早く離陸させよう
実際に計算してみよう
-15
-27
-13
0
s
-25
-22
t
着陸から離陸までの時間を，Ford法（高速化版）の適用
によって求めてみよう！（OHP利用）
101
ダイクストラ法
枝の費用が非負のネットワークに対する
最短路問題の代表的なアルゴリズム
だいたいの教科書にはこれが最初に
書いてある．
102
ダイクストラ法（アイディア）
点の走査順序を「点が一度走査されたら、それ以降
走査する必要がない」ことが肝要
枝の費用が非負ならば，そのようにできる
ポテンシャルが最小の点を走査すれば，
その点はその後走査する必要はない（なぜか？）
やってみよう
103
ダイクストラ法（やってみよう）
∞
1
1
∞
t
10
0
s
3
5
ポテンシャル
最小の点を走査
2
2
∞
2
6
3
∞
104
ダイクストラ法（やってみよう）
∞→10
1
1
∞
t
10
0
s
3
5
6
2
2
∞→5
2
3
∞
105
ダイクストラ法（やってみよう）
10
1
1
∞
t
10
ポテンシャル
最小の点を走査
2
0
s
3
5
走査済み
2
5
2
6
3
∞
106
ダイクストラ法（やってみよう）
10→8
1
1
∞
t
10
0
s
3
5
6
2
2
5
2
3
∞→7
107
ダイクストラ法（やってみよう）
8
1
1
∞
t
10
ポテンシャル
最小の点を走査
2
0
s
3
5
2
5
2
6
3
7
108
ダイクストラ法（やってみよう）
8
1
1
∞→13
t
10
0
s
3
5
6
2
2
5
2
3
7
109
ダイクストラ法（やってみよう）
8
1
1
13
t
10
ポテンシャル
最小の点を走査
2
0
s
3
5
2
5
2
6
3
7
110
ダイクストラ法（やってみよう）
8
1
1
13→9
t
10
0
s
3
5
6
2
2
5
2
3
7
111
ダイクストラ法（やってみよう）
8
1
1
9
t
10
0
s
3
5
2
2
5
終了
2
6
3
7
112
ダイクストラ法（きちんと書くと）
Dijkstra法
ポテンシャルyの初期設定
S:=V
while Sが空でないならば do
yvが最小の点 v  S を選択
S:=S＼{v}
点vの走査
113
演習問題１
1. Aから各点への最短路をDijkstra法で求めてみよう．
A
B
4
E
5
4
9
3
C
F
3
10
注：無向グラフなので
A->B,B->Ａの両方向に
枝がある有向グラフと
みなして解くこと！
3
D
4
114
演習問題２
 自分の家（下宿もしくは実家）から大
学までの交通機関を表すネットワーク
を作成し，最短時間のパスおよび最小
費用を求めよ．
注：移動時間や費用の計算には，「駅
前探検クラブ」http://ekitan.com/
などを利用して良いが，最短路は自分
で計算して求めること．
115
最短路問題をGurobiで解こう！
流通最適化工学
補助資料
単純な実装
from gurobipy import *
E, cost = multidict(
{(0,1):10, (0,2):5, (1,2):2, (1,4):1, (2,1):3,
(2,3):2, (3,4):6}
E= [(0, 1), (1, 2), (2, 3), (1, 4), (3, 4),
)
(0, 2), (2, 1)]
cost= {(0, 1): 10, (1, 2): 2, (2, 3): 2, (1,
V=range(5)
4): 1, (3, 4): 6, (0, 2): 5, (2, 1): 3}
print "E=",E
print "cost=",cost
multidict( ) 関数は，辞書を入力
キー（枝）のリスト，費用を表す辞書 cost
を返す．
モデルの構築
m=Model()
x={}
for (i,j) in E:
x[i,j] = m.addVar(name="x(%s,%s)"%(i,j))
m.update()
m.addConstr(
m.addConstr(
m.addConstr(
m.addConstr(
m.addConstr(
-x[0,1] - x[0,2] == -1 , name="source")
x[0,1] + x[2,1] -x[1,2] -x[1,4] ==0 , name="1" )
x[0,2] + x[1,2] -x[2,1] -x[2,3] ==0 , name="2")
x[2,3] - x[3,4] ==0 , name="3")
x[1,4] + x[3,4] ==1 , name="sink")
m.setObjective(quicksum( cost[i,j]*x[i,j] for (i,j) in E ), GRB.MINIMIZE)
m.optimize()
結果の出力
最適値
Optimal
Value= 9.0
0 1 0.0
1 2 0.0
最適解
1 4 1.0
for c in m.getConstrs():
2 3 0.0
print c.ConstrName, c.Pi
2 1 1.0
3 4 0.0
0 2 1.0
モデルオブジェクト m のgetConstrs()メソ
source -5.0
ッドで制約オブジェクトのリストを得る
最適双対解 1 3.0
各制約 c に対して，ConstrNameで制約名，
2 0.0
Pi（π）で双対変数を得る！
3 2.0
sink 4.0
print "Optimal Value=",m.ObjVal
for (i,j) in x:
print i,j,x[i,j].X
より一般的な実装
from gurobipy import *
E, cost = multidict(
{(0,1):10, (0,2):5, (1,2):2, (1,4):1, (2,1):3, (2,3):2,
(3,4):6}
)
隣接する点のリスト Out, Inの準備
V=range(5)
Out= [[1, 2], [2, 4], [3, 1], [4], []]
Out =[ [] for i in V ]
In= [[], [0, 2], [1, 0], [2], [1, 3]]
In =[ [] for i in V ]
for (i,j) in E:
Out[i].append(j)
In[j].append(i)
print "Out=",Out
print "In=",In
モデルの構築
m=Model()
x={}
for (i,j) in E:
x[i,j] = m.addVar(name="x(%s,%s)"%(i,j))
m.update()
for i in V:
if i==0:
m.addConstr( quicksum( x[i,j] for j in Out[i]) ==1 )
elif i==4:
m.addConstr( quicksum( x[j,i] for j in In[i]) ==1 )
else:
m.addConstr( quicksum( x[j,i] for j in In[i]) ==
quicksum( x[i,j] for j in Out[i]) )
m.setObjective(quicksum( cost[i,j]*x[i,j] for (i,j) in E ), GRB.MINIMIZE)
モデルの確認
m.update()
m.write("sp.lp")
モデル更新 update()の後で
Writeメソッド
ファイル “sp.lp” が
出力される
Minimize
10 x(0,1) + 2 x(1,2) + 2 x(2,3)
+ x(1,4) + 6 x(3,4) + 5 x(0,2) + 3
x(2,1)
Subject To
R0: x(0,1) + x(0,2) = 1
R1: x(0,1) - x(1,2) - x(1,4) +
x(2,1) = 0
R2: x(1,2) - x(2,3) + x(0,2) x(2,1) = 0
R3: x(2,3) - x(3,4) = 0
R4: x(1,4) + x(3,4) = 1
Bounds
End

Download Report