第十一章 最短路問(wèn)題

1、 一、引例例1：已知如圖所示的單行線交通網(wǎng)，每弧旁的數(shù)字表示通過(guò)這條單行線所需的費(fèi)用。現(xiàn)在某人要從v1出發(fā)通過(guò)v21621v3v3v52v96410 33這個(gè)交通網(wǎng)到v8 旅行路線。，求使總費(fèi)用最小的126v410v62v7 4 v8對(duì)于有向圖G 或無(wú)向圖G 的每一條邊e ，附加一個(gè)實(shí)數(shù)w(e),則稱(chēng)w(e)為邊e 上的權(quán)，當(dāng)e=(vi,vj)時(shí)，w(e)也可記為wij 。G 連同其各邊上的權(quán)稱(chēng)為帶權(quán)圖，帶權(quán)圖常記為G=。 最短路問(wèn)題：設(shè)G 是帶權(quán)圖，vs,vt是G 的兩個(gè)頂點(diǎn)，P是G 中從vs到vt的一條通路，定義路P 的權(quán)為P 中所有邊的權(quán)之和，記為w(P)。最短路就是在所有從vs到vt的

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

3、短路的權(quán)的上界（稱(chēng)為T(mén) 標(biāo)號(hào)），方法的每步是去修改T 標(biāo)號(hào)，并把某個(gè)T 標(biāo)號(hào)的點(diǎn)改變?yōu)榫哂蠵 標(biāo)號(hào)的點(diǎn)，從而使G 中具有P 標(biāo)號(hào)的頂點(diǎn)數(shù)多一個(gè)，這樣，至多經(jīng)過(guò)p1步，就可以求出從vs到各點(diǎn)的最短路。以引例為例，說(shuō)明標(biāo)號(hào)法的基本思想。s =1,因所有wij0，故d(v1,v1)=0,這時(shí)v1 是具有P 標(biāo)號(hào)的點(diǎn)?？疾鞆膙1出發(fā)的三條弧(v1,v2), (v1,v3),(v1,v4) 。如果從v1出發(fā)沿(v1,v2)到達(dá)v2, 則需要d(v1,v1)+w12=6單位費(fèi)用；如果v216216v3v312v410v52v96410 33v7 4 v8v62從v1出發(fā)沿(v1,v3)到達(dá)v3 ，則需要d

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

5、,v4)+w46=1+10=11單位。因?yàn)閙in d(v1,v1)+w12 , d(v1,v1)+w13 , d(v1,v4)+w46= d(v1,v1)+w13=3所以從v1出發(fā)到達(dá)v3所需要的最小費(fèi)用必定是3 單位，即從v1到v3的最短路是(v1,v3) ，d(v1,v3)=3 。v3變成具有P 標(biāo)號(hào)點(diǎn)。如此重復(fù)此過(guò)程，可以求出從v1到任意一點(diǎn)的最短路。幾個(gè)記號(hào)：用P ，T 分別表示某點(diǎn)具有P 標(biāo)號(hào)，T 標(biāo)號(hào)，用Si 表示第i 步時(shí)具有P 標(biāo)號(hào)點(diǎn)的集合。在每個(gè)點(diǎn)v 處給一個(gè)l值l (v) 。如果算法結(jié)束時(shí)， l(v) =m ，表示從vs 到v 的最短路上，v的前一個(gè)點(diǎn)是vm ；如果l(v)

6、 =M ，則表示G 中不含從vs 到v 的最短路；如果l(v) =0，則表示v =vs 。 Dijkstra方法的步驟：開(kāi)始（i =0）令S0 =vs ,P(vs )=0 , l(vs) =0 ,對(duì)每個(gè)v vs ,令T(v)=+,l (v)=M ，令k = s。（1）如果Si =V ，算法終止，這時(shí)，對(duì)每個(gè)v Si ,d(vs ,v) =P(v);否則轉(zhuǎn)（2）（2） 考察每個(gè)使(vk ,vj) E ,且vj Si 的點(diǎn)vj 。如果T(vj)P(vk) +wkj ,則把T(vj) 修改為P(vk) +wkj ,把l (vj) 修改為k； 否則轉(zhuǎn)入（3） 。(3)令T (vji) = min T

7、(v j )v j Sij如果T (v) i+,則把v的Tji標(biāo)號(hào)變?yōu)镻標(biāo)號(hào)，P(v)ji= T (v),ji令Si+1= Si vji, k =ji 把i換成i+ 1, 轉(zhuǎn)入（1）；否則終止，這時(shí)對(duì)每個(gè)v Si , d (vs , v) =P(v), 而對(duì)每個(gè)v Si , d (vs , v)= T (v) i=0 : S0=v1 , P(v1) = 0 , l (v1) =0 ,v21v5T(vi)=+, l (v) =M ,(i =2,3, ,9) , k=1(2)因?yàn)?v1 ,v2) E ,且v2 S0, P(v1)+w12T(v2), 把T(v2)修改為P(v1)+w12=6 ,l(

8、v2) 修改為1；6216v3v312v4102v96410 33v7 4 v8v62同理，把T(v3)修改為P(v1)+w13=3 , l (v3)修改為1 ；把T(v4)修改為P(v1)+w14=1, l(v4)修改為1。（3） 在所有的T 標(biāo)號(hào)中，T(v4)=1最v21v5小，令P(v4)=1,令S1=S0v4 , k=4 。622v96 i=1 :(2)把T(v6)修改為P(v4)+w46=11 ,v13v3410 33l (v6)修改為4126v410v62v7 4 v8（3）在所有的T 標(biāo)號(hào)中，T(v3)=3最小，令P(v3)=3,令S2=v1,v4,v3 , k=3 。 i=2

9、:(2)把T(v2)修改為P(v3)+w32=5 , l(v2)修改為3（3）在所有的T 標(biāo)號(hào)中，T(v2)=5最小,令P(v2)=5,令S3=v1,v4,v3,v2, k=2 。 i=3 :(2)把T(v5)修改為P(v2)+w25=6 , l (v5)修改為2（3）在所有的T 標(biāo)號(hào)中，T(v5)=6最小,令P(v5)=6 , 令S4=v1,v4,v3,v2,v5,k=5 。 i=4:(2)把T(v6) ,T(v7) ,T(v8)分別v21v5修改為10，9，12 ； l (v6)， l (v7)，l (v8)修改為5621v3v3642v9610 33（3）在所有的T 標(biāo)號(hào)中，T(v7)=

10、9最小,12v令P(v7)=9 , 令S5=v1,v4,v3,v2,v5 ,v7,vv2 v7 48k=7。4106 i=5:(2)因T(v8)P(v7)+w78 , 所以T(v8)不變（3）在所有的T 標(biāo)號(hào)中，T(v6)=10最小,令P(v6)=10 , 令S6=v1,v4,v3,v2,v5 ,v7 ,v6,k=6。 i=6:在所有的T 標(biāo)號(hào)中，T(v8)=12最小,令P(v8)=12 , 令最短路：(v1,v3,v2,v5,v8)d(v1,v8)=12S7=v1,v4,v3,v2,v5 ,v7 ,v6,v8 ,k=8。 i=7:T(v9)=+ ，算法終止。算法終止時(shí)：d(v1,vi)=P(

11、vi) , i =1 ,2 , , 8 ;從v1到v9不存在路。例2求右圖所示帶權(quán)圖中從v1到 v8的最短路解：這里只給出結(jié)果v2126v32v13v52v96433P(v1P(v5)=0 , P(v4)=6 , P(v9)=1 , P(v3)=8 , P(v7)=3 , P(v2)=9 , P(v6)=5 ,)=10 ,16v410v62v7 4 v8P(v8)=11; l(v1)=0 , l(v4)=1 , l(v3)=1 , l(v2)=3 , l(v5)=2, l(v9)=5 ,l(v7)=5 , l(v6)=5, l(v8)=9 。最短路：(v1,v3,v2,v5,v9,v8) ,

12、d(v1,v8)=11v例3求右圖中從v0到v5 的最短路0用標(biāo)號(hào)法解題時(shí)，可將計(jì)算過(guò)程用一張圖表來(lái)表示。v17v31252346v5v21v4vkiv00012345v111/v0v2433/v1v3+ 8877/v41252346v1v4+ 644/v27v5+ + + 1099/v3v3 最短路：T=v v v v v vv0012435v21v4例3 設(shè)備更新問(wèn)題第1年第2年第3年第4年第5年1111121213某企業(yè)使用一臺(tái)設(shè)備，每年年初，經(jīng)理就要決定是購(gòu)置新設(shè)備，還 是繼續(xù)使用舊的。若購(gòu)置新設(shè)備，就要支付一定的購(gòu)置費(fèi)；若繼續(xù) 使用舊的，則需要支付一定的維修費(fèi)?，F(xiàn)在的問(wèn)題是如何制定一個(gè) 幾年之內(nèi)的設(shè)備更新計(jì)劃，使得總的支付費(fèi)用最少。我們用一個(gè)五 年內(nèi)要更新某設(shè)備的計(jì)劃為例，若該種設(shè)備在各年年初的價(jià)格為下 表1；還已知使用不同時(shí)間的設(shè)備所需維修費(fèi)為下表2。使用年數(shù)0112233445維修費(fèi)用56811