第三节最短路问题

§8.3.最短路问题一、

引例单行线交通网：v1到v8使总费用最小的旅行路线。(下页图）最短路问题的一般描述：对D=（V，A），a=（vi，vj），w（a）=wij，P是vs到vt的路，定义路P的权是P中所有弧的权的和，记为w（P），则最短路问题为：路P0的权称为从vs到vt的距离，记为：d（vs，vt）V1V6V3V4V5V2V7V8V9622410341026613213

最短路问题就是从给定的网络图中找出一点到各点或任意两点之间距离最短的一条路.

有些问题，如选址、管道铺设时的选线、设备更新、投资、某些整数规划和动态规划的问题，也可以归结为求最短路的问题。因此这类问题在生产实际中得到广泛应用。例8.4渡河游戏 一老汉带了一只狼、一只羊、一棵白菜想要从南岸过河到北岸，河上只有一条独木舟，每次除了人以外，只能带一样东西；另外，如果人不在，狼就要吃羊，羊就要吃白菜，问应该怎样安排渡河，才能做到既把所有东西都运过河去，并且在河上来回次数最少？这个问题就可以用求最短路方法解决。定义：1）人—M（Man），狼—W（Wolf），羊—G（Goat），草—H（Hay）2）点——vi

表示河岸的状态3）边——ek

表示由状态vi

经一次渡河到状

态vj

4）权——边ek

上的权定为1我们可以得到下面的加权有向图状态说明：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)此游戏转化为在下面的二部图中求从v1

到u1

的最短路问题。v1v2v3v4v5u5u4u3u2u1求最短路有两种算法:

狄克斯屈拉(Dijkstra)标号算法逐次逼近算法

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

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

Dijkstra算法基本思想：采用标号法:P标号和T标号P标号：已确定出最短路的节点(永久性标号)。T标号：未确定出最短路的节点，但表示其距离的上限(试探性标号)。算法的每一步都把某一点的T标号改为P标号直至改完为止.Si：第i步时P标号节点的集合。λ(v)：最短路中前一个节点的编号。初始值：

Dijkstra算法基本步骤

Step1:给vs以P标号,P(vs)=0,其余各点均给T标号,T(vi)=+∞

Step2:若vj点为刚得到P标号的点,考虑这样的点vj,(vi,vj)∈E,且vj为T标号.

Step3:对vj的T标号进行如下更改:T（vj）=min[T（vj），P（vi）+lij]

Step4:比较所有具有T标号的点,把最小者改为P标号.

当存在两个以上最小值时,可同时改为P标号.

若全部改为P标号,则停止.否则转回(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的点，转向③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的点，转向③

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

总结:

算法步骤:例8.5求下图v1到v7的最短路长及最短路线①②③④⑤⑥⑦862523534210570862254411147510711P标号T标号9v1到v7的最短路长及最短路线如图所示：①②③④⑤⑥⑦86252353421057v7已标号，计算结束。从v1到v7的最短路长是11,最短路线：v1→v4→v6

→v702411从上例知，只要某点已标号，说明已找到起点vs到该点的最短路线及最短距离，因此可以将每个点标号，求出vs到任意点的最短路线，如果某个点vj不能标号，说明vs不可达vj

。注：无向图最短路的求法只将上述步骤2将弧改

成边即可。例8.6求下图v1到各点的最短距离及最短路线。①②③④⑤⑥⑦⑧4526178393261216180452231039612641166188122482418v1到各点的最短距离及最短路线如图所示：①②③④⑤⑥⑦⑧45261783932612161802618所有点都已标号，点上的标号就是v1到该点的最短距离，最短路线就是红色的链。237184566134105275934682练习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