- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
• Step1 -更新與S集合內所有點相鄰的點之d(x) -d(x)=min{d(x),d(s)+a(s,x)} • Step2 -S={ j | d(j) 在step1更新過 } -T(j)=S集合內為j點的上游點 • Step3
when k<=(n-1) & S , k=k+1 , go to Step1 when k<=(n-1) & S , Stop when k=n & S , Stop
• Step2 設 d ( x) min{d ( x), d ( y ) a( y, x)} • a(y,x)代表y到x點的距離,當y點沒有節線 到達x點時, a(y,x)=無限大
10 10 Ex: s x t a(s,x)=a(x,t)=10 , a(s,t)=a(x,s)=a(t,x)=無限大
Y
Y {2 L={0,1, ∞,4} ,4} P={0,1,0,1} L={0,1,2,4} {3} P={0,1,2,1} Y L={0,1,2,3} {4} P={0,1,2,3}
Y
習題
1. 用forward star的形式建立此路網的data base 2. 用label setting 與 label correcting Algorithm 求解點1到各點的最短路徑
– 取d(x)中最小的一個的x (非s且不曾為y)為y Ex: d(s)=0 , d(a)=5 , d(b)=7 , d(c)=6 , y=a
• Step3 當y=t時,即找到s到t的最短路徑 否則重新執行Step2
紀錄路徑
• 在撰寫程式時,為方便知道路徑經過哪些點,建 議設一變數P(x)代表通過x點是經過P(x)點到 達的 • Ex
s
a
b
t
P(a)=s , P(b)=a , P(t)=b
例子
• 已知一路網
4
1
7
3
2
2
2
s
3
t 4
2
3
3
d(s)=0 d(1)=∞
d(2)=∞
d(3)=∞ d(4)=∞ d(t)=∞
4
1 7 2 t
y=s
s
3
3
4
d(s)=0 d(1)=min{d(1) , d(s) + a(s,1)}=min{∞,0+4}=4
1 9
3
1 7 3 5 6 8 4
2
3 5 7
4
7
6
7
9
5 3 8
6
9
10
4
2
5
Label Correcting Algorithm
Ford(1946) , Moore(1957) , Bellman(1958)
• 已知一路網有n點,起點s d k ( x) :從起點s經k階到達x的距離 Lk :在k階時, d k ( x) 的集合 S k :從起點開始,恰k階到達的點(終點)集合 P k :k階時,所有點的前置點集合 ( S ) :S集合內所有點的下游點的集合
d(2)=min{d(2) , d(s) + a(s,2)}=min{∞,0+7}=7
d(3)=min{d(3) , d(s) + a(s,3)}=min{∞,0+3}=3 d(4)=∞ d(t)=∞
4
1 7 2 t
y=3
S到3最短距離為3
s
3
3
3
4
d(s)=0 d(1)=4
d(2)=7 d(3)=3(已做過y)
d(4)=min{d(4) , d(3) + a(3,4)}=min{∞,3+3}=6 d(t)=∞
4
1 3 7 2 t
y=1
S到1最短距離為4
s
3ห้องสมุดไป่ตู้
3
3
4
d(s)=0 d(1)=4(已做過y)
d(2)=min{d(2) , d(1) + a(1,2)}=min{7,4+3}=7 d(3)=3(已做過y)
何為“階”: 一階 二階 三階
K*
• 該點的K*表示在進行到某階時,起點到 該點的最短路徑中,該點的上一點為何 • Ex
2 1 3 上圖為node 1 到node 3 的最短路 徑,則node 3的K*為2
Algorithm
• 起始條件 k=0 , d(s)=0 , d ( x) when x s S={s} , k=k+1 , go to Step1
例題
4 4 1 2 1
1
1
3
k ( S ) j T(j) 0
d(x) d(1)=0
k*
update
Distanc Label S L={0,∞, ∞, ∞} {1}
d(2)=min{ 1 {2,4} 2 {1} ∞,0+1}=1 1 d(4)=min{ 4 {1} ∞,0+4}=4 1 d(3)=min{ 2 {3} 3 {2} ∞,1+1}=2 2 d(4)=min{ 3 {4} 4 {3} 4,2+1}=3 3
Label Setting Algorithm
Dijkstra’s Shortest-Path Algorithm (Label Setting Algorithm )
• 已知路網中有K個點,假設其中兩點分別為 s & t,欲求 s到t的最短路徑 • Step1 設一變數d(x)代表s點到x點的距離 (x代表路網中任一點) d ( x) when x s d ( x ) 0 when x s 定義y=s
Distance 6 3 2 2 2 1 3 1 3 5
Forward star
1
3
6
(1)Point 1
(2)Point 4
2
2
3
3
(3)Point 7 (4)Point 8 (5)Point 9
2 3 2
1
4
1
5
5
6
需25儲存格
To Distance 2 6 4 3 5 2 3 2 5 2 6 1 6 3 5 1 2 3 6 5
d(4)=6 d(t)=∞
4
1 3 7 2 t
y=4
S到4最短距離為6
s
3
3
3
2
4
d(s)=0 d(1)=4(已做過y)
d(2)=7 d(3)=3(已做過y)
d(4)=6(已做過y) d(t) =min{d(t) , d(4) + a(4,t)}=min{∞,6+2}=8
4
1 3 7 2 2 t
y=2
S到2最短距離為7
s
3
3
3
2
4
d(s)=0 d(1)=4(已做過y)
d(2)=7(已做過y)
d(3)=3(已做過y) d(4)=6(已做過y) d(t) =min{d(t) , d(2) + a(2,t)}=min{8,7+2}=8
4
1 3 7 2 2 t
y=8
s
S到t最短距離為8
3
3
3
2
4
Label Correcting Algorithm
運輸資訊
最短路徑演算法
卓訓榮 2002/11/11 Data base Label Setting Algorithm Label Correcting Algorithm
Data Base
1
3
6
2
2
3
3
2 3 2
1
4
1
5
5
6
需30儲存格
From 1 1 1 2 2 2 3 4 5 5
To 2 4 5 3 5 6 6 5 2 6
