第三節(jié)最短路問題

§8.3.最短路問題一、

引例單行線交通網(wǎng)：v1到v8使總費(fèi)用最小的旅行路線。(下頁圖）最短路問題的一般描述：對D=（V，A），a=（vi，vj），w（a）=wij，P是vs到vt的路，定義路P的權(quán)是P中所有弧的權(quán)的和，記為w（P），則最短路問題為：路P0的權(quán)稱為從vs到vt的距離，記為：d（vs，vt）V1V6V3V4V5V2V7V8V9622410341026613213

最短路問題就是從給定的網(wǎng)絡(luò)圖中找出一點(diǎn)到各點(diǎn)或任意兩點(diǎn)之間距離最短的一條路.

有些問題，如選址、管道鋪設(shè)時(shí)的選線、設(shè)備更新、投資、某些整數(shù)規(guī)劃和動(dòng)態(tài)規(guī)劃的問題，也可以歸結(jié)為求最短路的問題。因此這類問題在生產(chǎn)實(shí)際中得到廣泛應(yīng)用。例8.4渡河游戲 一老漢帶了一只狼、一只羊、一棵白菜想要從南岸過河到北岸，河上只有一條獨(dú)木舟，每次除了人以外，只能帶一樣?xùn)|西；另外，如果人不在，狼就要吃羊，羊就要吃白菜，問應(yīng)該怎樣安排渡河，才能做到既把所有東西都運(yùn)過河去，并且在河上來回次數(shù)最少？這個(gè)問題就可以用求最短路方法解決。定義：1）人—M（Man），狼—W（Wolf），羊—G（Goat），草—H（Hay）2）點(diǎn)——vi

表示河岸的狀態(tài)3）邊——ek

表示由狀態(tài)vi

經(jīng)一次渡河到狀

態(tài)vj

4）權(quán)——邊ek

上的權(quán)定為1我們可以得到下面的加權(quán)有向圖狀態(tài)說明：v1,u1=(M,W,G,H);v2,u2=(M,W,G);v3,u3=(M,W,H);v4,u4=(M,G,H);v5,u5=(M,G)此游戲轉(zhuǎn)化為在下面的二部圖中求從v1

到u1

的最短路問題。v1v2v3v4v5u5u4u3u2u1求最短路有兩種算法:

狄克斯屈拉(Dijkstra)標(biāo)號(hào)算法逐次逼近算法

Dijkstra算法：適用于有向圖，wij≥0基本原理

如：假定v1→v2→v3→v4是v1→v4的最短路，則v1→v2→v3一定是v1→v3的最短路，v2→v3→v4也一定是v2→v4的最短路。v1v2v3v4v5

Dijkstra算法基本思想：采用標(biāo)號(hào)法:P標(biāo)號(hào)和T標(biāo)號(hào)P標(biāo)號(hào)：已確定出最短路的節(jié)點(diǎn)(永久性標(biāo)號(hào))。T標(biāo)號(hào)：未確定出最短路的節(jié)點(diǎn)，但表示其距離的上限(試探性標(biāo)號(hào))。算法的每一步都把某一點(diǎn)的T標(biāo)號(hào)改為P標(biāo)號(hào)直至改完為止.Si：第i步時(shí)P標(biāo)號(hào)節(jié)點(diǎn)的集合。λ(v)：最短路中前一個(gè)節(jié)點(diǎn)的編號(hào)。初始值：

Dijkstra算法基本步驟

Step1:給vs以P標(biāo)號(hào),P(vs)=0,其余各點(diǎn)均給T標(biāo)號(hào),T(vi)=+∞

Step2:若vj點(diǎn)為剛得到P標(biāo)號(hào)的點(diǎn),考慮這樣的點(diǎn)vj,(vi,vj)∈E,且vj為T標(biāo)號(hào).

Step3:對vj的T標(biāo)號(hào)進(jìn)行如下更改:T（vj）=min[T（vj），P（vi）+lij]

Step4:比較所有具有T標(biāo)號(hào)的點(diǎn),把最小者改為P標(biāo)號(hào).

當(dāng)存在兩個(gè)以上最小值時(shí),可同時(shí)改為P標(biāo)號(hào).

若全部改為P標(biāo)號(hào),則停止.否則轉(zhuǎn)回(2).V1V6V3V4V5V2V7V8V9622410341026613213V1V6V3V4V5V2V7V8V9622410341026613213

i=0

，s0={v1}，P（v1）=0，

λ（v1）=0，

k=1T(v2)=+∞，λ（v2

)=MT(v3)=+∞,λ

（v3

)=M

。。。。。。

T(v9)=+∞,λ

（v9

)=MV1V6V3V4V5V2V7V8V9622410341026613213P(v1)=0,λ(v1)=0T(v2)=+,λ(v2)=MT(v3)=+,λ(v3)=MT(v4)=+,λ(v4)=MT(v6)=+,λ(v6)=MT(v7)=+,λ(v7)=MT(v5)=+,λ(v5)=MT(v8)=+,λ(v8)=MT(v9)=+,λ(v9)=+

V1V6V3V4V5V2V7V8V9622410341026613213P(v1)=0,λ(v1)=0T(v2)=+,λ(v2)=MT(v3)=+,λ(v3)=MT(v4)=+,λ(v4)=MT(v6)=+,λ(v6)=MT(v7)=+,λ(v7)=MT(v5)=+,λ(v5)=MT(v8)=+,λ(v8)=MT(v9)=+,λ(v9)=+

V1V6V3V4V5V2V7V8V9622410341026613213P(v1)=0,λ(v1)=0T(v2)=+,λ(v2)=MT(v3)=+,λ(v3)=MT(v4)=+,λ(v4)=MT(v6)=+,l(v6)=MT(v7)=+,l(v7)=MT(v5)=+,λ(v5)=MT(v8)=+,l(v8)=MT(v9)=+,λ(v9)=+

②（v1,,,v2):P(v1)+l12=0+6=6<T(v2)

修改T(v2)=6,λ(v2)=1

（v1,,,v3):P(v1)+l13=0+3=3<T(v3)T(v3)=3,λ(v3)=1

（v1,,,v4):P(v1)+l14=0+1=1<T(v4)T(v4)=1,λ(v4)=1V1V6V3V4V5V2V7V8V9622410341026613213P(v1)=0,λ(v1)=0T(v2)=+,l(v2)=MT(v3)=+,l(v3)=MT(v4)=+,l(v4)=MT(v6)=+,l(v6)=MT(v7)=+,l(v7)=MT(v5)=+,λ(v5)=MT(v8)=+,l(v8)=MT(v9)=+,λ(v9)=+

T(v2)=6,λ(v2)=1T(v4)=1,λ(v4)=1T(v3)=3,λ(v3)=1②（v1,,,v2):P(v1)+l12=0+6=6<T(v2)T(v2)=6,λ(v2)=1

（v1,,,v3):P(v1)+l13=0+3=3<T(v3)T(v3)=3,λ(v3)=1

（v1,,,v4):P(v1)+l14=0+1=1<T(v4)T(v4)=1,λ(v4)=1V1V6V3V4V5V2V7V8V9622410341026613213P(v1)=0,λ(v1)=0T(v2)=6,λ(v2)=1T(v4)=1,λ(v4)=1T(v3)=3,λ(v3)=1T(v6)=+,λ(v6)=MT(v7)=+,λ(v7)=MT(v5)=+,λ(v5)=MT(v8)=+,l(v8)=MT(v9)=+,λ(v9)=+

min{T（v2），T(v3),T(v4),T(v5),T(v6),T(v7),T(v8),T(v9),}=T(v4),令P（v4）=1，k=4

i=1，S1={v1，v4}V1V6V3V4V5V2V7V8V9622410341026613213P(v1)=0,λ(v1)=0T(v2)=6,λ(v2)=1P(v4)=1,

λ(v4)=1T(v3)=3,λ(v3)=1T(v6)=+,λ(v6)=MT(v7)=+,λ(v7)=MT(v5)=+,λ(v5)=MT(v8)=+,l(v8)=MT(v9)=+,λ(v9)=+

min{T（v2），T(v3),T(v4),T(v5),T(v6),T(v7),T(v8),T(v9),}=T(v4),令P（v4）=1，k=4i=1，S1={v1，v4}V1V6V3V4V5V2V7V8V9622410341026613213P(v1)=0,l(v1)=0T(v2)=6,l(v2)=1P(v4)=1,

l(v4)=1

T(v3)=3,l(v3)=1T(v6)=+,l(v6)=MT(v7)=+,l(v7)=MT(v5)=+,l(v5)=MT(v8)=+,l(v8)=MT(v9)=+,l(v9)=+

V1V6V3V4V5V2V7V8V9622410341026613213P(v1)=0,l(v1)=0T(v2)=6,l(v2)=1P(v4)=1,

l(v4)=1

T(v3)=3,l(v3)=1T(v6)=+,l(v6)=MT(v7)=+,l(v7)=MT(v5)=+,l(v5)=MT(v8)=+,l(v8)=MT(v9)=+,l(v9)=+

（v4，v6）：P（v4）+l46=1+10=11<T(v6)

修改T(v6)=11,λ(v6)=4T(v6)=11,l(v6)=4V1V6V3V4V5V2V7V8V9622410341026613213P(v1)=0,l(v1)=0T(v2)=6,l(v2)=1P(v4)=1,

l(v4)=1

T(v3)=3,l(v3)=1T(v6)=11,l(v6)=4T(v7)=+,l(v7)=MT(v5)=+,l(v5)=MT(v8)=+,l(v8)=MT(v9)=+,l(v9)=+

（v4，v6）：P（v4）+l46=1+10=11<T(v6)

修改T(v6)=11,λ(v6)=4V1V6V3V4V5V2V7V8V9622410341026613213P(v1)=0,l(v1)=0T(v2)=6,l(v2)=1P(v4)=1,

l(v4)=1T(v3)=3,l(v3)=1T(v6)=11,l(v6)=4T(v7)=+,l(v7)=MT(v5)=+,l(v5)=MT(v8)=+,l(v8)=MT(v9)=+,l(v9)=+

min{T（v2），T(v3),T(v5),T(v6),T(v7),T(v8),T(v9)}=T(v3),令P（v3）=3，k=3

i=2，S2={v1，v4,v3}V1V6V3V4V5V2V7V8V9622410341026613213P(v1)=0,l(v1)=0T(v2)=6,l(v2)=1P(v4)=1,

l(v4)=1

P(v3)=3,

l(v3)=1

T(v6)=11,l(v6)=4T(v7)=+,l(v7)=MT(v5)=+,l(v5)=MT(v8)=+,l(v8)=MT(v9)=+,l(v9)=+

min{T（v2），T(v3),T(v5),T(v6),T(v7),T(v8),T(v9)=T(v3),i=2，S2={v1，v4,v3}，P（v3）=3，k=3min{T（v2），T(v3),T(v5),T(v6),T(v7),T(v8),T(v9)}=T(v3),令P（v3）=3，k=3

i=2，S2={v1，v4,v3}V1V6V3V4V5V2V7V8V9622410341026613213P(v1)=0,l(v1)=0T(v2)=6,l(v2)=1P(v4)=1,

l(v4)=1

P(v3)=3,

l(v3)=1

T(v6)=11,l(v6)=4T(v7)=+,l(v7)=MT(v5)=+,l(v5)=MT(v8)=+,l(v8)=MT(v9)=+,l(v9)=+

T(v2)=5,l(v2)=3（v3，v2）：P（v3）+l32=3+2=5<T(v2)=6

修改T(v2)=5,λ(v2)=3V1V6V3V4V5V2V7V8V9622410341026613213P(v1)=0,l(v1)=0T(v2)=5,l(v2)=3P(v4)=1,

l(v4)=1

P(v3)=3,

l(v3)=1

T(v6)=11,l(v6)=4T(v7)=+,l(v7)=MT(v5)=+,l(v5)=MT(v8)=+,l(v8)=MT(v9)=+,l(v9)=+

（v3，v2）：P（v3）+l32=3+2=5<T(v2)=6T(v2)=5,λ(v2)=3V1V6V3V4V5V2V7V8V9622410341026613213P(v1)=0,l(v1)=0T(v2)=5,l(v2)=3P(v4)=1,

l(v4)=1

P(v3)=3,

l(v3)=1

T(v6)=11,l(v6)=4T(v7)=+,l(v7)=MT(v5)=+,l(v5)=MT(v8)=+,l(v8)=MT(v9)=+,l(v9)=+

min{T（v2）,T(v5),T(v6),T(v7），T(v8),T(v9)}=T(v2),令P（v2）=5，k=2

i=3，S2={v1，v4,v3,v2}V1V6V3V4V5V2V7V8V9622410341026613213P(v1)=0,l(v1)=0P(v2)=5,

l(v2)=3

P(v4)=1,

l(v4)=1

P(v3)=3,

l(v3)=1

T(v6)=11,l(v6)=4T(v7)=+,l(v7)=MT(v5)=+,l(v5)=MT(v8)=+,l(v8)=MT(v9)=+,l(v9)=+

min{T（v2）,T(v5),T(v6),T(v7),T(v8),T(v9)}=T(v2),i=3，S2={v1，v4,v3,v2}，P（v2）=5，k=2min{T（v2）,T(v5),T(v6),T(v7），T(v8),T(v9)}=T(v2),令P（v2）=5，k=2

i=3，S2={v1，v4,v3,v2}V1V6V3V4V5V2V7V8V9622410341026613213P(v1)=0,l(v1)=0P(v2)=5,l(v2)=3P(v4)=1,

l(v4)=1

P(v3)=3,

l(v3)=1

T(v6)=11,l(v6)=4T(v7)=+,l(v7)=MT(v5)=+,l(v5)=MT(v8)=+,l(v8)=MT(v9)=+,l(v9)=+

T(v5)=6,l(v5)=2（v2，v5）：P（v2）+l25=5+1=6<T(v5)

修改T(v5)=6,λ(v5)=2V1V6V3V4V5V2V7V8V9622410341026613213P(v1)=0,l(v1)=0P(v2)=5,l(v2)=3P(v4)=1,

l(v4)=1

P(v3)=3,

l(v3)=1T(v6)=11,l(v6)=4T(v7)=+,l(v7)=MT(v5)=6,l(v5)=2T(v8)=+,l(v8)=MT(v9)=+,l(v9)=+

（v2，v5）：P（v2）+l25=5+1=6<T(v5)T(v5)=6,λ(v5)=2V1V6V3V4V5V2V7V8V9622410341026613213P(v1)=0,l(v1)=0P(v2)=5,l(v2)=3P(v4)=1,

l(v4)=1

P(v3)=3,

l(v3)=1T(v6)=11,l(v6)=4T(v7)=+,l(v7)=MT(v5)=6,l(v5)=2T(v8)=+,l(v8)=MT(v9)=+,l(v9)=+

min{T(v5),T(v6),T(v7),T(v8),T(v9)}=T(v2),

令P（v5）=6，k=5

i=4，S4={v1，v4,v3,v2,v5}V1V6V3V4V5V2V7V8V9622410341026613213P(v1)=0,l(v1)=0P(v2)=5,l(v2)=3P(v4)=1,

l(v4)=1

P(v3)=3,

l(v3)=1

T(v6)=11,l(v6)=4T(v7)=+,l(v7)=MP(v5)=6,l(v5)=2T(v8)=+,l(v8)=MT(v9)=+,l(v9)=+

min{T(v5),T(v6),T(v7),T(v8),T(v9)}=T(v2),i=4，S4={v1，v4,v3,v2,v5}，P（v5）=6，k=5min{T(v5),T(v6),T(v7),T(v8),T(v9)}=T(v2),

令P（v5）=6，k=5

i=4，S4={v1，v4,v3,v2,v5}V1V6V3V4V5V2V7V8V9622410341026613213P(v1)=0,l(v1)=0P(v2)=5,l(v2)=3P(v4)=1,

l(v4)=1P(v3)=3,

l(v3)=1T(v6)=11,l(v6)=4T(v7)=+,l(v7)=MP(v5)=6,l(v5)=2T(v8)=+,l(v8)=MT(v9)=+,l(v9)=+

T(v6)=10,l(v6)=5T(v7)=9,l(v7)=5T(v8)=12,l(v8)=5②（v5,,,v6):P(v5)+l56=6+4=10<T(v6)

修改T(v10)=10,λ(v6)=5

（v5,,,v7):P(v5)+l57=6+3=9<T(v7)T(v7)=9,λ(v7)=5

（v5,,v8):P(v5)+l58=6+6=12<T(v8)T(v8)=12,λ(v8)=5V1V6V3V4V5V2V7V8V9622410341026613213P(v1)=0,l(v1)=0P(v2)=5,l(v2)=3P(v4)=1,

l(v4)=1

P(v3)=3,

l(v3)=1

T(v6)=10,l(v6)=5T(v7)=9,l(v7)=5P(v5)=6,l(v5)=2T(v8)=12,l(v8)=5T(v9)=+,l(v9)=+

②（v5,,,v6):P(v5)+l56=6+4=10<T(v6)

修改T(v10)=10,λ(v6)=5

（v5,,,v7):P(v5)+l57=6+3=9<T(v7)T(v7)=9,λ(v7)=5

（v5,,v8):P(v5)+l58=6+6=12<T(v8)T(v8)=12,λ(v8)=5V1V6V3V4V5V2V7V8V9622410341026613213P(v1)=0,l(v1)=0P(v2)=5,l(v2)=3P(v4)=1,

l(v4)=1

P(v3)=3,

l(v3)=1

T(v6)=10,l(v6)=5T(v7)=9,l(v7)=5P(v5)=6,l(v5)=2T(v8)=12,l(v8)=5T(v9)=+,l(v9)=+

min{T(v6),T(v7),T(v8),T(v9)}=T(v7)

令P（v7）=9，k=7

i=5，S5={v1，v4,v3,v2,v5，v7}V1V6V3V4V5V2V7V8V9622410341026613213P(v1)=0,l(v1)=0P(v2)=5,l(v2)=3P(v4)=1,

l(v4)=1

P(v3)=3,

l(v3)=1

T(v6)=10,l(v6)=5P(v7)=9,

l(v7)=5

P(v5)=6,l(v5)=2T(v8)=12,l(v8)=5T(v9)=+,l(v9)=+

min{T(v6),T(v7),T(v8),T(v9)}=T(v7)

令P（v7）=9，k=7

i=5，S5={v1，v4,v3,v2,v5，v7}V1V6V3V4V5V2V7V8V9622410341026613213P(v1)=0,l(v1)=0P(v2)=5,l(v2)=3P(v4)=1,

l(v4)=1

P(v3)=3,

l(v3)=1

T(v6)=10,l(v6)=5P(v7)=9,

l(v7)=5

P(v5)=6,l(v5)=2T(v8)=12,l(v8)=5T(v9)=+,l(v9)=+

（v7，v8）：P（v7）+l78=9+4=13>T(v8)T(v8),λ(v5)不變V1V6V3V4V5V2V7V8V9622410341026613213P(v1)=0,l(v1)=0P(v2)=5,l(v2)=3P(v4)=1,

l(v4)=1

P(v3)=3,

l(v3)=1

T(v6)=10,l(v6)=5P(v7)=9,

l(v7)=5

P(v5)=6,l(v5)=2T(v8)=12,l(v8)=5T(v9)=+,l(v9)=+

（v7，v8）：P（v7）+l78=9+4=13>T(v8)T(v8),λ(v5)不變V1V6V3V4V5V2V7V8V9622410341026613213P(v1)=0,l(v1)=0P(v2)=5,l(v2)=3P(v4)=1,

l(v4)=1

P(v3)=3,

l(v3)=1

T(v6)=10,l(v6)=5P(v7)=9,

l(v7)=5

P(v5)=6,l(v5)=2T(v8)=12,l(v8)=5T(v9)=+,l(v9)=+

P(v6)=10,l(v6)=5min{T(v6),T(v8),T(v9)}=T(v6)

令P（v6）=10，k=6

i=6，S6={v1，v4,v3,v2,v5，v7,v6}V1V6V3V4V5V2V7V8V9622410341026613213P(v1)=0,l(v1)=0P(v2)=5,l(v2)=3P(v4)=1,

l(v4)=1P(v3)=3,

l(v3)=1

P(v6)=10,l(v6)=5P(v7)=9,

l(v7)=5

P(v5)=6,l(v5)=2T(v8)=12,l(v8)=5T(v9)=+,l(v9)=+

min{T(v6),T(v8),T(v9)}=T(v6)

令P（v6）=10，k=6

i=6，S6={v1，v4,v3,v2,v5，v7,v6}V1V6V3V4V5V2V7V8V9622410341026613213P(v1)=0,l(v1)=0P(v2)=5,l(v2)=3P(v4)=1,

l(v4)=1

P(v3)=3,

l(v3)=1

P(v6)=10,l(v6)=5P(v7)=9,

l(v7)=5

P(v5)=6,l(v5)=2T(v8)=12,l(v8)=5T(v9)=+,l(v9)=+

v6無指向不屬于S6的點(diǎn)，轉(zhuǎn)向③V1V6V3V4V5V2V7V8V9622410341026613213P(v1)=0,l(v1)=0P(v2)=5,l(v2)=3P(v4)=1,

l(v4)=1

P(v3)=3,l(v3)=1P(v6)=10,l(v6)=5P(v7)=9,

l(v7)=5

P(v5)=6,l(v5)=2P(v8)=12,l(v8)=5T(v9)=+,l(v9)=+

min{T(v8),T(v9)}=T(v8)

令P（v8）=12，k=8

i=7，S7={v1，v4,v3,v2,v5，v7,v6，v8}V1V6V3V4V5V2V7V8V9622410341026613213P(v1)=0,l(v1)=0P(v2)=5,l(v2)=3P(v4)=1,

l(v4)=1

P(v3)=3,

l(v3)=1P(v6)=10,l(v6)=5P(v7)=9,

l(v7)=5

P(v5)=6,l(v5)=2P(v8)=12,

l(v8)=5

T(v9)=+,l(v9)=+

v8無指向不屬于S7的點(diǎn)，轉(zhuǎn)向③

min{T（v9）}=+∞T（v9）=+∞算法終止

總結(jié):

算法步驟:例8.5求下圖v1到v7的最短路長及最短路線①②③④⑤⑥⑦862523534210570862254411147510711P標(biāo)號(hào)T標(biāo)號(hào)9v1到v7的最短路長及最短路線如圖所示：①②③④⑤⑥⑦86252353421057v7已標(biāo)號(hào)，計(jì)算結(jié)束。從v1到v7的最短路長是11,最短路線：v1→v4→v6

→v702411從上例知，只要某點(diǎn)已標(biāo)號(hào)，說明已找到起點(diǎn)vs到該點(diǎn)的最短路線及最短距離，因此可以將每個(gè)點(diǎn)標(biāo)號(hào)，求出vs到任意點(diǎn)的最短路線，如果某個(gè)點(diǎn)vj不能標(biāo)號(hào)，說明vs不可達(dá)vj

。注：無向圖最短路的求法只將上述步驟2將弧改

成邊即可。例8.6求下圖v1到各點(diǎn)的最短距離及最短路線。①②③④⑤⑥⑦⑧4526178393261216180452231039612641166188122482418v1到各點(diǎn)的最短距離及最短路線如圖所示：①②③④⑤⑥⑦⑧45261783932612161802618所有點(diǎn)都已標(biāo)號(hào)，點(diǎn)上的標(biāo)號(hào)就是v1到該點(diǎn)的最短距離，最短路線就是紅色的鏈。237184566134105275934682練習(xí)1：

求從1到8的最短路徑237184566134105275934682X={1},w1=0min{c12,c14,c16}=min{0+2,0+1,0+3}=min{2,1,3}=1X={1,4},p4=1p4=1p1=0237184566134105275934682X={1,4}min{c12,c16,c42,c47}=min{0+2,0+3,1+10,1+2}=min{2,3,11,3}=2X={1,2,4},p2=2p1=0p4=1p2=2237184566134105275934682X={1,2,4}min{c16,c23,c25,c47}=min{0+3,2+6,2+5,1+2}=min{3,8,7,3}=3X={1,2,4,6},p6=3p2=2p4=1p1=0p6=3237184566134105275934682X={1,2,4,6}min{c23,c25,c47,c67}=min{2+6,2+5,1+2,3+4}=min{8,7,3,7}=3X={1,2,4,6,7},p7=3p2=2p4=1p1=0p6=3p7=3237184566134105275934682X={1,2,4,6,7}min{c23,c25,c75,c78}=min{2+6,2+5,3+3,3+8}=min{8,7,6,11}=6X={1,2,4,5,6,7},p5=6p2=2p4=1p1=0p6=3p7=3p5=6237184566134105275934682X={1,2,4,6,7}min{c23,c53,c58,c78}=min{2+6,6+9,6+4,3