资源描述：
《项目管理关键路径算法(PMP)课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、最短路徑演算法卓訓榮2002/11/11DatabaseLabelSettingAlgorithmLabelCorrectingAlgorithm運輸資訊DataBase1234566233152213FromToDistance126143152232252261363451523565需30儲存格1234566233152213需25儲存格ToDistance26435232526163512365(1)Point1(2)Point4(3)Point7(4)Point8(5)Point9For
2、wardstarLabelSettingAlgorithmDijkstra’sShortest-PathAlgorithm (LabelSettingAlgorithm)已知路網中有K個點,假設其中兩點分別為s&t,欲求s到t的最短路徑Step1設一變數d(x)代表s點到x點的距離(x代表路網中任一點)whenwhen定義y=sStep2設a(y,x)代表y到x點的距離,當y點沒有節線到達x點時,a(y,x)=無限大Ex:a(s,x)=a(x,t)=10,a(s,t)=a(x,s)=a(t,x)=
3、無限大取d(x)中最小的一個的x(非s且不曾為y)為yEx:d(s)=0,d(a)=5,d(b)=7,d(c)=6,y=atxs1010Step3當y=t時,即找到s到t的最短路徑否則重新執行Step2紀錄路徑在撰寫程式時,為方便知道路徑經過哪些點,建議設一變數P(x)代表通過x點是經過P(x)點到達的ExP(a)=s,P(b)=a,P(t)=bsabt例子已知一路網s1234t43373222s1234td(s)=0d(1)=∞d(2)=∞d(3)=∞d(4)=∞d(t)=∞y=s473s123
4、4td(s)=0d(1)=min{d(1),d(s)+a(s,1)}=min{∞,0+4}=4d(2)=min{d(2),d(s)+a(s,2)}=min{∞,0+7}=7d(3)=min{d(3),d(s)+a(s,3)}=min{∞,0+3}=3d(4)=∞d(t)=∞y=34733S到3最短距離為3s1234td(s)=0d(1)=4d(2)=7d(3)=3(已做過y)d(4)=min{d(4),d(3)+a(3,4)}=min{∞,3+3}=6d(t)=∞y=147333S到1最短距離為4
5、s1234td(s)=0d(1)=4(已做過y)d(2)=min{d(2),d(1)+a(1,2)}=min{7,4+3}=7d(3)=3(已做過y)d(4)=6d(t)=∞y=4473332S到4最短距離為6s1234td(s)=0d(1)=4(已做過y)d(2)=7d(3)=3(已做過y)d(4)=6(已做過y)d(t)=min{d(t),d(4)+a(4,t)}=min{∞,6+2}=8y=24733322S到2最短距離為7s1234td(s)=0d(1)=4(已做過y)d(2)=7(已做過
6、y)d(3)=3(已做過y)d(4)=6(已做過y)d(t)=min{d(t),d(2)+a(2,t)}=min{8,7+2}=8y=84733322S到t最短距離為8LabelCorrectingAlgorithmLabelCorrectingAlgorithmFord(1946),Moore(1957),Bellman(1958)已知一路網有n點,起點s:從起點s經k階到達x的距離:在k階時,的集合:從起點開始,恰k階到達的點(終點)集合:k階時,所有點的前置點集合:S集合內所有點的下游點的集
7、合何為“階”:一階二階三階K*該點的K*表示在進行到某階時,起點到該點的最短路徑中,該點的上一點為何Ex123上圖為node1到node3的最短路徑,則node3的K*為2Algorithm起始條件k=0,d(s)=0,whenS={s},k=k+1,gotoStep1Step1-更新與S集合內所有點相鄰的點之d(x)-d(x)=min{d(x),d(s)+a(s,x)}Step2-S={j
8、d(j)在step1更新過}-T(j)=S集合內為j點的上游點Step3whenk<=(n-1)&,k=k
9、+1,gotoStep1whenk<=(n-1)&,Stopwhenk=n&,Stop例題12341114kjT(j)d(x)k*updateDistancLabelS0d(1)=0L={0,∞,∞,∞}{1}1{2,4}2{1}d(2)=min{∞,0+1}=11Y4{1}d(4)=min{∞,0+4}=41YL={0,1,∞,4}{2,4}P={0,1,0,1}2{3}3{2}d(3)=min{∞,1+1}=22YL={0,1,2,4}{3}P={0,1,2,1}3{4}4{3
