Document

情報通信工学科情報通信基礎学講座
平成14年度卒業研究発表
最短路問題 -Partitionアルゴリズム-
9712066 小林英之
安藤研究室
Dijkstraのアルゴリズム
Step 1. s = (start point)
d(x) : s から x への仮の距離
（ S の点のみを経由する最短路の長さ）
d(s) = 0 , d(x) = ∞ for x≠s
S = { s からの距離確定点}
Step 2. S に含まれない d(x) が最小の点を探し、
それを S に加えることで順次 S を増大させ
目的の点に到達する
Partitionアルゴリズム
Step 1. s = (start point)
d(s) = 0, d(x) = ∞ for x≠s
NOW = {s},NEXT = {φ}
Step 2. NOWから任意に点 u を選んでくる。
NOW = {φ} →Step 4
Step 3.NOWから点 u を削除する。
d(u) + a(u,v) < d(v)
であれば
d(v) = d(u) + a(u,v)
NOW・NEXTに v の要素がなければ、
NEXTに加える。
NOW = {φ}→Step4
Step 4. NEXT = {φ}→終了
NEXT ≠{φ}→NOW = NEXT →Step2
改良Partitionアルゴリズム
Step 4A. NEXT = {φ}→終了
NEXT ≠{φ}→NEXTから何点か
選び出してNOWに移す →Step2
Step 4B. NEXT = {φ}→終了
NEXT ≠{φ}→NEXTからc個の頂点
を選び出してNOWに移す →Step2
d(x) 1 2 3 4 5 6 7 8
0 ∞ ∞ ∞ ∞ ∞ ∞ ∞
9
2
4
2
7
0 1 6 ∞ 1 ∞ ∞ ∞
4
0 1 6 10 1 ∞ ∞ ∞
1
6
1
1
3
5
3
3
8
8
2
6
0 1 4 10 1 ∞ ∞ ∞
0 1 4 10 1 6 ∞ 7
0 1 4 10 1 6 12 7
0 1 4 10 1 6 11 7
NOW
1 2 3 4 5 6 7 8
NEXT
2 3 4 5 6 7 8
d(x) 1 2 3 4 5 6 7 8
0 ∞ ∞ ∞ ∞ ∞ ∞ ∞
9
2
4
2
7
1
4
6
1
1
3
5
NOW
3
3
8
8
2
6
1 2 3 4 5 6 7 8
NEXT 1 2 3 4 5 6 7 8
参考文献
• James R. Evans, Edward Minieka, “Optimization
Algorithms For Networks And Graphs Second
Edition Revised And Expanded”, MARCEL
DEKKER, INC., 1992
• Glover, F., D Klingman, and N.Philips, A New
Polynomially Bounded Shortest Path Algorithm,
Oper.Res., 33, (1985), pp.65-73.
• 浅野孝夫・今井浩,アルゴリズムの基礎,オーム
社,2000

Download Report