1
2
3 6
4
5 7
6,20
5,10
10,8 6,6
2,5
8,7
4,5 5,2
3,8
7,5
5,7
4,20
＜クラスカル法＞
(0)
グラフG
の枝を短い順に並べ、a 1 ≦ a 2 ≦
・・・ ≦ a m
を満たすように枝e iの番号（添字）
を付けかえる． Ｔ：＝
{e
1}
，k
：＝2
とおく．(1)
枝集合Ｔ∪{e
k}
が閉路を含まないならば、Ｔ：＝Ｔ∪
{e
k}
とする．(2)
ＴがG
の全域木になっていれば計算終了．さもなければ
k
：＝k+1
としてステップ(1)
へ．J.B.Kruskal (1956)
欲張り法（
Greedy Algorithm
）1
2
3 6
4
7 5
6
5
10 6
2
8
4 5
3
7
5
4
１．(1)
最小木1
2 3
4 5
6
＜ダイクストラ法＞
(0) S
：＝φ
，S
：＝V
，d(s)
：＝0
，である節点
v ∈ S
を選ぶ．(2) S
：＝S ∪ {v}
，S
：＝S
－{v})
とする．E.Dijkstra (1959)
d(i)
：＝∞ (i ∈ V
－{s})
とおく．(1) S
＝V
なら計算終了．そうでないなら，d(v)
＝min{d(i)
｜i ∈ S}
d(j)
＞d(v)
＋a vj ならば d(j)
：＝ d(v)
＋ a vj
（
(v,j) ∈ E
，j ∈ S
）p(j)
：＝v
とし，ステップ(1)
へ．1
2
3 6
4
7 5
6
5
10 6
2
8
4 5
3
7
5
4
１．(2)
最短路１．
(2) (a)
0
(6)
(5)
1
2
3 6
4
7 5
6
5
10 6
2
8
4 5
3
7
5
4
0
(6)
1
2
3 6
4
7 5
6
5
10 6
2
8
4 5
3
7
5
4
0
5
(6)
(15) (11)
１．
(2) (b)
１．
(2) (c)
5
1
2
3 6
4
7 5
6
5
10 6
2
8
4 5
3
7
5
4
0
5
6
(15) (10)
(14)
1
2
3 6
4
7 5
6
5
10 6
2
8
4 5
3
7
5
4
0
5
6
(13)
10
(14)
１．(2) (d)
1
2
3 6
4
7 5
6
5
10 6
2
8
4 5
3
7
5
4
0
5
6
13 10
(14)
1
2
3 6
4
7 5
6
5
10 6
2
8
4 5
3
7
5
4
0
5
6
13 10
(14)
(17)
1
2
3 6
4
7 5
6
5
10 6
2
8
4 5
3
7
5
4
0
5
6
13 10
14
(17)
1
2
3 6
4
7 5
6
5
10 6
2
8
4 5
3
7
5
4
0
5
6
13 10
14
17
1
2
3 6
4
7 5
6
5
10 6
2
8
4 5
3
7
5
4
１．(3)
最長路1
2
3 6
4
5 7 6
5
10 6
2
8
4 5
3
7
5
4
0
5
6
1
2
3 6
4
5 7 6
5
10 6
2
8
4 5
3
7
5
4
0
8
6
１．
(3) (a)
１．
(3) (b)
1
2
3 6
4
7 5
6
5
10 6
2
8
4 5
3
7
5
4
0
8
6
14
1
2
3 6
4
7 5
6
5
10 6
2
8
4 5
3
7
5
4
0
8
6
14
19
１．
(3) (c)
1
2
3 6
4
7 5
6
5
10 6
2
8
4 5
3
7
5
4
0
8
6
14
19
26
1
2
3 6
4
7 5
6
5
10 6
2
8
4 5
3
7
5
4
0
8
6
14
19
26
30
＜フロー増加法＞
(0)
適当な初期フローx
を定める(
例えばx
ij=0) (1)
フロー増加路を見つける．存在しなければ計算終了．
(2)
フロー増加路に沿って可能な限りフローを追加し，新しいフロー
x
を得る．ステップ(1)
に戻る．1
2
3 6
4
5 7 20
10
8 6
5
7
5 2
8
5
7
20
２．(1)
最大流1
2
3 6
4
7 5
20
10
8 6
5
7
5 2
8
5
7
20
1
2
3 6
4
7 5
13
2
8 6
5
7
5 2
8
5
7
12
8
フロー7
フロー8 7
8
15
フロー２．
(1) (a)
２．
(1) (b)
1
2
3 6
4
7 5
13
2
8 6
5
7
5 2
8
5
7
12 8
7 8
2
フロー2
フロー1
2
3 6
4
7 5
11
8 4
5
7
3 2
6
3
7
8 12 9
10
2
2
19
フロー2 2
２．
(1) (c)
1
2
3 6
4
7 5
11
8 4
5
7
3 2
6
3
7
8 12 9
10
2
2
23
フロー2 2
4
フロー1
2
3 6
4
7 5
7
8 1
7
3 2
2
3
7
4 16 13
10
2
2
6 6
4
2
フロー1
2
3 6
4
7 5
7
8 1
7
3 2
2
3
7
4 16 13
10
2
2
6 6
4
25
フロー1
2
3 6
4
7 5
5
8 1
7
1 2
3
7
2 18 15
10
4
2
6 8
4
終了
1
2
3 6
4
5 7 20(15)
10(10)
8(8) 6(6)
5(4)
7(7)
5(4) 2(2)
8(8)
5(2)
7(7)
20(18)
最大流流量２５
＜負閉路除去法＞
(0)
適当な初期フローx
を定める(1)
残余ネットワークG
x=(V,E
x)
において負閉路 を見つける．存在しなければ計算終了．(2)
負閉路に沿って可能な限りフローを追加し，新しいフロー
x
を得る．ステップ(1)
に戻る．２．
(2)
最小費用流1
2
3 6
4
5 7 6,20
5,10
10,8 6,6
2,5
8,7
4,5 5,2
3,8
7,5
5,7
4,20
(1)
で求めた最大流1
2
3 6
4
5 7 6,20(15)
5,10(10)
10,8(8) 6,6(6)
2,5(4)
8,7(7) 4,5(4) 5,2(2)
3,8(8)
7,5(2)
5,7(7)
4,20(18)
総コスト：
90+50+8+56+16+36+80+10+24+14+35+72=491
1
2
3 6
4
5 7 6,20(15)
5,10(10)
10,8(8) 6,6(6)
2,5(4)
8,7(7) 4,5(4) 5,2(2)
3,8(8)
7,5(2)
5,7(7)
4,20(18)
1
2
3 6
4
7 5
6,5
-10,8 2,1
4,1 -8,7 -5,2
7,3
-5,7
4,2 -4,18 -6,15
-5,10
-4,4
-7,2 -6,6 -3,8
-2,4
２．(2) (a)
1
2
3 6
4
5 7 6,5
-10,8 2,1
-8,7
4,1 -5,2
7,3
-5,7
4,2 -4,18
-6,15
-5,10
-4,4 -7,2
-6,6 -3,8 -2,4
閉路：２
→
５→
３→
２コスト：
4+(-6)+(-2)=-4
１フロー 総コスト：491-4=487
２．
(2) (b)
1
2
3 6
4
7 5
6,5
-10,8 2,1
-8,7
4,1 -5,2
7,3
-5,7
4,2 -4,18
-6,15
-5,10
-4,4 -7,2
-6,6 -3,8 -2,4
1
2
3 6
4
7 5
6,5
-10,8 2,2
-8,7
-5,2
7,3
-5,7
4,2 -4,18
-6,15
-5,10
-4,5
-7,2 -6,5 -3,8
-2,3
２．(2) (c)
1
2
3 6
4
5 7 6,20(15)
5,10(10)
10,8(8) 6,6(5)
2,5(3)
8,7(7) 4,5(5) 5,2(2)
3,8(8)
7,5(2)
5,7(7)
4,20(18)
流量２５の最小費用流総コスト：
487
３．
O(n 3 )
の場合10
分間：10
9×600
＝６×10
11回の演算n=10
3 ならばn 3 =109
n=10
4 ならばn 3 =1012
したがって
(c)
O(n 2 )
の場合n=10
5 ならばn 2 =1010
n=10
6 ならばn 2 =1012
したがって
(e) n=10
3～10
4n=10
5～10
6計算機の演算数：
10
分間：10
9×600
＝６×10
11回の演算計算量：
O(n)
の場合(f)
計算量：O(n
2)
の場合(e)
計算量：
