最短路問題

有些問題，如選址、管道鋪設時的選線、設備更新、投資、某些整數規劃和動態規劃的問題，也可以歸結為求最短路的問題。因此這類問題在生產實際中得到廣泛應用。求最短路有兩種算法，一是求從某一點至其它各點之間最短離的狄克斯屈拉(Dijkstra)算法；另一種是求網圖上任意兩點之間最短的矩陣算法。最短路問題，就是從給定的網絡圖中找出一點到各點或任意兩點之間距離最短的一條路.4/8/2025渡河問題一老漢帶了一只狼、一只羊、一棵白菜想要從南岸過河到北岸，河上只有一條獨木舟，每次除了人以外，只能帶一樣東西；另外，如果人不在，狼就要吃羊，羊就要吃白菜，問應該怎樣安排渡河，才能做到既把所有東西都運過河去，并且在河上來回次數最少？這個問題就可以用求最短路方法解決。設：M—人

W—狼

S—羊

V—白菜渡河方案共有10種，構造如下一個圖，每條邊的距離為1，問題變為求一條從MWSV到φ的最短路。北岸南岸4/8/2025狄克斯屈拉(Dijkstra)標號算法點標號：b(j)—起點vs到點vj的最短路長；邊標號：k(i，j)=b(i)+dij，步驟：1.令起點的標號；b(s)＝0。先求有向圖的最短路，設網絡圖的起點是vs,終點是vt,以vi為起點vj為終點的弧記為（i，j）,距離為dij

2.找出所有vi已標號vj未標號的弧集合B=｛（i，j）｝如果這樣的弧不存在或vt已標號則計算結束；3.計算集合B中弧k(i，j)=b(i)+dij的標號4.選一個點標號返回到第2步。4/8/2025【例】求下圖v1到v7的最短路長及最短路線①②③④⑤⑥⑦86252353421057086225441114751071211v7已標號，計算結束。從v1到v7的最短路長是11最短路線是：v1v4v6

v74/8/2025從上例知，只要某點已標號，說明已找到起點vs到該點的最短路線及最短距離，因此可以將每個點標號，求出vs到任意點的最短路線，如果某個點vj不能標號，說明vs不可達vj

.無向圖最短路的求法無向圖最短路的求法只將上述步驟2改動一下即可。點標號：b(i)—起點vs到點vj的最短路長；邊標號：k(i，j)=b(i)+dij，步驟：1.令起點的標號；b(s)＝0。3.計算集合B中邊標號：k[i，j]=b(i)+dij4.選一個點標號:返回到第2步。

2.找出所有一端vi已標號另一端vj未標號的邊集合B=｛[i，j]｝如果這樣的邊不存在或vt已標號則計算結束；4/8/2025【例】求下圖v1到各點的最短路及最短距離①②③④⑤⑥⑦⑧4526178393261216180452231039612641166188122482418所有點都已標號，點上的標號就是v1到該點的最短距離，最短路線就是紅色的鏈。進入演示和練習4/8/2025有負權的最短路算法假設圖中沒有負回路。如下圖是一條負回路，最短路權無下界。①②③3－2－2當vi到vj之間沒有弧連接時，令wij＝＋∞列表迭代計算：設vs到vj經過vi到達vj，則vs到vj的最短距離為：迭代：4/8/2025【例】求下圖v1到v8的最短路長及最短路線4/8/2025wijv1v2v3v4v5v6v7v8k=1k=2k=3k=4v10－1－2300v2602－1v3－30－51－2v4023v5－10v61017v7－10v8－3－50＋min＝－5＋min＝－2－71－150＋min＝－5－2－7－3－1－560－5－2－7－3－1－564/8/2025wijv1v2v3v4v5v6v7v8k=1k=2路線距離v10－1－231-11-11-10v26021-21-3-21-3-2－5v3－30－511-41-31-3－2v4021-3-41-3-4－7v5－101-2-51-3-2-5－3v610171-3-61-3-6－1v7－101-4-71-3-4-7－5v8－3－501-3-6-864/8/2025**任意兩點間最短距離的矩陣算法**（選講）【例】在下圖中用矩陣計算法求各點之間的最短距離【解】定義dij為圖中兩相鄰點的距離，若i與j不相鄰，令dij=∞。則①②③④⑤⑥⑦527276243164/8/2025步驟:1.4/8/2025應用（教材P270例4）年份12345購置費1111121213維修費5681118①②③④⑤⑥161617171822304159223041233123最優更新方案：1.第一年和第三年購置新設備；2.第一年和第四年購置新設備?？傎M用為