最短路模型課件

1、關(guān)于最短路模型第一張，PPT共十二頁，創(chuàng)作于2022年6月一、引例例1：已知如圖所示的單行線交通網(wǎng)，每弧旁的數(shù)字表示通過這條單行線所需的費用?，F(xiàn)在某人要從v1出發(fā)通過這個交通網(wǎng)到v8 ，求使總費用最小的旅行路線。對于有向圖G 或無向圖G 的每一條邊e ，附加一個實數(shù)w(e),則稱w(e)為邊e 上的權(quán)，當e=(vi,vj)時，w(e)也可記為wij 。G 連同其各邊上的權(quán)稱為帶權(quán)圖，帶權(quán)圖常記為G=。最短路問題：設(shè)G 是帶權(quán)圖，vs,vt是G 的兩個頂點，P是G 中從vs到vt的一條通路，定義路P 的權(quán)為P 中所有邊的權(quán)之和，記為w(P)。最短路就是在所有從vs到vt的路中，求一條權(quán)最小的路，

2、即求一條從vs到vt的路P0,使v6v5v4v3v2v1v9v8v7310461022161234263第二張，PPT共十二頁，創(chuàng)作于2022年6月上式中對G 中所有從vs到vt的路P 取最小，稱P0為從vs到vt的最短路。路P0的權(quán)稱為從vs到vt的距離，記為d(vs,vt),顯然d(vs,vt)與d(vt,vs)不一定相等。二、最短路算法設(shè)G=為n階帶權(quán)圖，wij0,若vi與vj 不相鄰，令wij=標號法：標號法是由E.W.Dijkstra于1959年提出來的，其基本思想是：從vs出發(fā)，逐步地向外探尋最短路。在執(zhí)行過程中，與每點對應(yīng)，記錄下一個數(shù)（稱為這個點的標號），它或者表示從vs到該點

3、的最短路的權(quán)（稱為P 標號），或者表示從vs 到該點的最短路的權(quán)的上界（稱為T 標號），方法的每步是去修改T 標號，并把某個T 標號的點改變?yōu)榫哂蠵 標號的點，從而使G 中具有P 標號的頂點數(shù)多一個，這樣，至多經(jīng)過p1步，就可以求出從vs到各點的最短路。以引例為例，說明標號法的基本思想。第三張，PPT共十二頁，創(chuàng)作于2022年6月s =1,因所有wij0，故d(v1,v1)=0, 這時v1 是具有P 標號的點。v6v5v4v3v2v1v9v8v7310461022161234263考察從v1出發(fā)的三條弧(v1,v2), (v1,v3),(v1,v4) 。如果從v1出發(fā)沿(v1,v2)到達v2,

4、則需要d(v1,v1)+w12=6單位費用；如果從v1出發(fā)沿(v1,v3)到達v3 ，則需要d(v1,v1)+w13=3單位費用；類似地若沿(v1,v4)到達v4 , 則需要d(v1,v1)+w14=1單位費用。由于min d(v1,v1)+w12 , d(v1,v1)+w13 , d(v1,v1)+w14= d(v1,v1)+w14=1所以從v1出發(fā)到達v4所需要的最小費用必定是1單位，即從v1到v4的最短路是(v1,v4) ，d(v1,v4)=1 。v4 變成具有P 標號點?？疾鞆膙1及v4指向的其余點的弧，由上已知，從v1出發(fā)分別沿(v1,v2)，(v1,v3) 到達v2,v3, 所需6

5、 ，3單位費用，而從v1出發(fā)沿(v1,v4)和(v4,v6)到達v6 ,所需費用是d(v1,v4)+w46=1+10=11單位。因為min d(v1,v1)+w12 , d(v1,v1)+w13 , d(v1,v4)+w46= d(v1,v1)+w13=3第四張，PPT共十二頁，創(chuàng)作于2022年6月所以從v1出發(fā)到達v3所需要的最小費用必定是3 單位，即從v1到v3的最短路是(v1,v3) ，d(v1,v3)=3 。v3變成具有P 標號點。如此重復(fù)此過程，可以求出從v1到任意一點的最短路。幾個記號：用P ，T 分別表示某點具有P 標號，T 標號，用Si 表示第i 步時具有P 標號點的集合。在每

6、個點v 處給一個值 (v) 。如果算法結(jié)束時， (v) =m ，表示從vs 到v 的最短路上，v 的前一個點是vm ；如果(v) =M ，則表示G 中不含從vs 到v 的最短路；如果 (v) =0，則表示v =vs 。Dijkstra方法的步驟：開始（i =0）令S0 =vs ,P(vs )=0 , (vs) =0 ,對每個v vs ,令T(v)=+, (v)=M ，令k = s 。（1）如果Si =V ，算法終止，這時，對每個v Si ,d(vs ,v) =P(v);否則轉(zhuǎn)（2）（2）考察每個使(vk ,vj) E ,且vj Si 的點vj 。第五張，PPT共十二頁，創(chuàng)作于2022年6月如果

7、T(vj)P(vk) +wkj ,則把T(vj) 修改為P(vk) +wkj ,把 (vj) 修改為k；否則轉(zhuǎn)入（3） 。v6v5v4v3v2v1v9v8v7310461022161234263i=0 : S0=v1 , P(v1) = 0 , (v1) =0 ,T(vi)=+, (v) =M ,(i =2,3, ,9) , k=1(2)因為(v1 ,v2) E ,且v2 S0, P(v1)+w12T(v2), 把T(v2)修改為P(v1)+w12=6 , (v2) 修改為1 ；同理，把T(v3)修改為P(v1)+w13=3 , (v3)修改為1 ；把T(v4)修改為P(v1)+w14=1,

8、(v4)修改為1 。第六張，PPT共十二頁，創(chuàng)作于2022年6月v6v5v4v3v2v1v9v8v7310461022161234263（3）在所有的T 標號中，T(v4)=1最小，令P(v4)=1,令S1=S0v4 , k=4 。i=1 : (2)把T(v6)修改為P(v4)+w46=11 , (v6)修改為4 （3）在所有的T 標號中，T(v3)=3最小，令P(v3)=3,令S2=v1,v4,v3 , k=3 。i=2 : (2)把T(v2)修改為P(v3)+w32=5 , (v2)修改為3 （3）在所有的T 標號中，T(v2)=5最小,令P(v2)=5,令S3=v1,v4,v3,v2 ,

9、 k=2 。i=3 : (2)把T(v5)修改為P(v2)+w25=6 , (v5)修改為2 （3）在所有的T 標號中，T(v5)=6最小,令P(v5)=6 , 令S4=v1,v4,v3,v2,v5 , k=5 。第七張，PPT共十二頁，創(chuàng)作于2022年6月i=4: (2)把T(v6) ,T(v7) ,T(v8)分別修改為10，9，12 ； (v6)， (v7)， (v8)修改為5 （3）在所有的T 標號中，T(v7)=9最小,令P(v7)=9 , 令S5=v1,v4,v3,v2,v5 ,v7 , k=7 。v6v5v4v3v2v1v9v8v7310461022161234263i=5: (2

10、)因T(v8)P(v7)+w78 , 所以T(v8)不變（3）在所有的T 標號中，T(v6)=10最小,令P(v6)=10 , 令S6=v1,v4,v3,v2,v5 ,v7 ,v6 , k=6 。i=6: 在所有的T 標號中，T(v8)=12最小,令P(v8)=12 , 令S7=v1,v4,v3,v2,v5 ,v7 ,v6,v8 , k=8 。i=7: T(v9)=+ ，算法終止。算法終止時：d(v1,vi)=P(vi) , i =1 ,2 , , 8 ;從v1到v9不存在路。最短路：(v1,v3,v2,v5,v8)d(v1,v8)=12第八張，PPT共十二頁，創(chuàng)作于2022年6月v6v5v4

11、v3v2v1v9v8v73461022161234263例2 求右圖所示帶權(quán)圖中從v1到 v8的最短路解：這里只給出結(jié)果P(v1)=0 , P(v4)=1 , P(v3)=3 , P(v2)=5 , P(v5)=6 , P(v9)=8 , P(v7)=9 , P(v6)=10 , P(v8)=11; (v1)=0 , (v4)=1 , (v3)=1 , (v2)=3 , (v5)=2, (v9)=5 , (v7)=5 , (v6)=5, (v8)=9 。最短路：(v1,v3,v2,v5,v9,v8) , d(v1,v8)=11例3 求右圖中從v0到v5 的最短路用標號法解題時，可將計算過程用一張圖表來表示。v5357421126v4v1v2v0v3第九張，PPT共十二頁，創(chuàng)作于2022年6月357421126v4v1v2v0v3最短路：T=v0v1v2v4v3v5 vk i v0 v1 v2 v3 v4 v501234501 1/v0433/v1+8877/v4+ 644/v2+ + + 1099/v3第十張，PPT共十二頁，創(chuàng)作于2022年6月例3 設(shè)備更新問題某企業(yè)使用一臺設(shè)備，每年年初，經(jīng)理就要決定是購置新設(shè)備，還是繼續(xù)使用舊的。若購置新設(shè)備，就要支付一定的購置費；若繼續(xù)使用舊的，則需要支付一定的維修費?，F(xiàn)在的問題是如何制