交大运筹学真题教案

第三节 最短路问题一、最短路问题例下图为单行线交通网，每弧旁的数字表示通过这条线所需的费用。现在某人要从v1出发，通过这个交通网到v8去，求使总费用最小的旅行路线。v2v53464v1v4v612v32106210v89v71

2v363从v1到v8：P1=（v1，v2，v5，v8）P2=（v1，v3，v4，

v6，

v7，

v8）费用6+1+6=13费用3+2+10+2+4=21P3=

……从v1到v8的旅行路线 从v1到v8的路。最短路问题中，不考虑有向环、并行弧。旅行路线总费用 路上所有弧权之和。v2v53464v1v4v612v321061210v89v3v7263最短路问题给定有向网络D=（V，A，W），任意弧aij∈A，有权w（

aij

）=wij，给定D中的两个顶点vs，vt。设P是D中从vs到vt的一条路，定义路P的权（长度）是P中所有弧的权之和，记为w（P）。最短路问题就是要在所有从vs到vt的路中，求一条路P0

，使w

(P0

)=

min

w

(P)P称P0是从vs到vt的最短路。路P0的权称为从vs到vt的路长。记为ust。二、Dijkstra算法当所有

wij

≥0

时，本算法是用来求给定点vs到任一个点vj

最短路的公认的最好方法。事实：如果P是D中从vs到vj的最短路，vi是P中的一个点，那么，从vs沿P到vi的路是从vs到vi的最短路。最短路的子路也是最短路。u1

=

min{wsi

}X0

=V\X0

,

则记X0

=

{vs

},vi

˛X0取最小值的点为v1，∴P1=P（vs，v1）假定u0，u1，…，uk的值已求出，对应的最短路分别为P1=P（vs，v1），

P2=P（vs，v2），…，

Pk=P（vs，vk）思想：将D=（V，A，W）中vs到所有其它顶点的最短路按其路长从小到大排列为：u0≤

u1

≤

u2

≤…≤

unu0表示vs到自身的长度，相应最短路记为：P0，P1，P2，…，Pn，P1一定只有一条弧。记则Xk

=

V

\

XkXk

=

{vs

,v1

,v2

,...,vk

}

,uk

+1

=

min

{ui

+

w(

vi

,

v'

)}vi

˛

X

kv

'˛

X

k使上式达到最小值的点v’可取为vk+1。计算过程中可采用标号方法。Xk中的点，ui值是vs到vi的最短路长度，相应的点记“永久”标号；XK中的点，ui值是vs到vi的最短路长度的上界，相应的点记“临时”标号，供进一步计算使用。前点标号li

:

表示点vs到vj的最短路上vj的前一点。如li=m，表示vs到vj的最短路上vj前一点是vm。1,6图上标号法:v5v2234643v1v41v21061210v8v9v72363v60,01,

∞1,

∞1,11,

∞1,

∞1,

∞1,31,6图上标号法:v5v2234643v1v41v21061210v8v9v72363v60,01,

∞1,

∞1,11,

∞1,

∞1,

∞1,31,6图上标号法:v5v2234643v1v41v21061210v8v9v72363v60,01,

∞4,111,11,

∞1,

∞1,

∞1,31,5图上标号法:v5v2234643v1v41v21061210v8v9v72363v60,01,

∞4,111,11,

∞1,

∞1,

∞1,31,61,5图上标号法:v5v2234643v1v41v21061210v8v9v72363v60,01,

∞4,111,11,

∞1,

∞1,

∞1,33,53,5图上标号法:v5v2234643v1v41v21061210v8v9v72363v60,01,

∞4,111,11,

∞1,

∞1,31,

∞3,5图上标号法:v5v2234643v1v41v21061210v8v9v72363v60,01,

∞4,111,11,

∞1,

∞1,31,

∞3,5图上标号法:v5v2234643v1v41v21061210v8v9v72363v60,04,111,11,

∞2,61,

∞1,31,∞3,5图上标号法:v5v2234643v1v41v21061210v8v9v72363v60,04,111,11,

∞2,61,

∞1,31,∞3,5图上标号法:v5v223464v1v41v321061210v8v9v72363v60,05,101,11,

∞2,65,121,35,93,5图上标号法:v5v2234643v1v41v21061210v8v9v72363v60,05,101,11,

∞2,65,121,35,9令li=i，uj=ui+wij否则,li,,uj返回第2步。不变,把k换成k+1，Dijkstra算法步骤：第1步：令us=

0，uj=wsj

（1≤j≤n）若asjˇA，则令wsj=+¥

,

X0={vs}

,X0=V\X0

,k=0,

li=0

(0

≤j≤n）第2步：(选永久标号)在XK中选一点vi，满足u

i

=min

{u

j

}如果ui=+¥，停止，第3步：（给点vi永久性标号）令Xk+1=Xk∪﹛vi﹜,Xk+1=Xk＼﹛vi﹜如果Xk+1

=F

，结束，到所有的点的最短路已经求得；否则，转第4步。第4步：(修改临时标号)

对所有

v

j

˛

X

k

+1

如,

果

ui

+

wij

<

ujv

j

˛

X

K从vs到XK中各点没有路；否则，转第3步。例

用Dijkstra算法求前面例子中从v1到各点的最短路。解：u1=0，u2=6，u3=3，u4=1，u5=u6=u7=u8=u9=+¥，lj=1

（j=2，3，…，9）X0={v1}

，X0={v2，v3，…，v9}v2v53464v1v4v612v32106210v89v3v71

263K=0

∵

min{u2，u3，u4，u5，u6，u7，u8，u9}=min{6，3，1，¥，¥，¥，¥，¥}=1=

u∴点v4得永久标号，l4=1

，X1={v1，v4}，X1={v2，v3，

v5，v6

，v7，v8

，v9}，在所有vj∈X1中，∵u6=¥

，u4+w46=1+10=11，即u4+w46<u6∴修改临时标号u6=11

，l6=4

，其余标号不变。v2v534464v1v4v612v32106210v89v3v71

263K=0

+1=1

∵

min{u2，u3，u5，u6，u7，u8，u9}=min{6，3，¥，

11，

¥，¥，¥}=3=

u3∴点v3得永久标号，l3=1

，X2={v1，v4

，v3}，X2={v2，

v5，v6

，v7，v8

，v9}，在所有vj∈X2中，∵u2=6

，u3+w32=3+2=5，即u3+w32<u2∴修改临时标号u2=5

，l2=3

，其余标号不变。k=2

+1=3

∵

min{u5，u6，u7，u8，u9}=min{6，11，

¥，¥，¥}=6=

u5∴点v5得永久标号，l5=2

，X4={v1，v4，v3，v2，v5}，X4={v6

，v7，v8，v9}，在所有vj∈X4中，∵u6=11

，u5+w56=6+4=10，即u5+w56<u6u7=¥

，u5+w57=6+3=9，即u5+w57<u7u8=¥

，u5+w58=6+6=12，即u5+w58<u8∴修改临时标号u6=10

，l6=5

，u7=9

，l7=5

，u8=

12

，l8=5

，K=3

+1=4

∵

min{u6，u7，u8，u9}=min{10，9，12，¥

}

=9=

u7∴点v7得永久标号，l7=5

，X2={v1，v4

，v3

，

v2，

v5，v7}，X2={v6

，v8

，v9}，在vj∈X5中，临时标号不变。K=4

+1=5

∵

min{u6，u8，u9}=min{10，12，¥}

=10=

u6∴点v6得永久标号，l6=5

，X6={v1，v4

，v3

，

v2，

v5，v7

，v6}，X6={v8

，v9}，点v8，v9临时标号不变。K=5

+1=6

∵

min{u8，u9}=min{12，¥}

=12=

u8∴点v8得永久标号，l8=5

，即从v1到v8的最短路长为u8=12，∵l8=5

，l5=2

，l2=3

，l3=1

，知从v1到v8

的最短路为：P1，8=P（v1，v3

，

v2，

v5，v8）v2v53464v1v4v612v32106210v89v3v71

263问题：①本例中，v1到v9的最短路？②无向网络:③负权弧时。wijvivjwijwijvji无向网络中，最短路→v最短链。v3④多个点对之间最短路？v1v212-3Dijkstra算法失效三、Floyd算法网络D=（V，A，W），令U=(uij)n·n，D中vi到vj的最短路的长度。uij

表示考虑D中任意两点vi，vj，如将D中vi，vj以外的点都删掉，得只剩vi，vj的一个子网络D0，记当v

i

,v

j

)˛

A

¥=

w

ij否则iju

(0)wij为弧（

vi，vj）的权。

vi在D0中加入v1及D中与vi，vj，v1相关联的弧，得D1，D1中vi到vj的最短路ij长记为u(1){}(0)1

j(0)i

1(0)ijiju(1),则一定有=

min

u+

u,

uvjv1wij再在D1中加入v2及D中与vi，vj，v1，v2相关联的ij弧，得D2，D2中vi到vj的最短路长记为u

(2)

，则有{

}(1)2

j(1)i

2(1)ijiju(2),

u+

u=

min

u递推，D中n个点逐个加入子网络，终得D中vi到vj的最短路路长ij

iju=

u

(n)如果计算结果希望给出具体的最短路的路径，则构造路径矩阵S=(sij)n·n

,sij表示vi到vj的最短路的第一条弧的终点。如的第一条弧为（

vi，vt），第二条弧为从vt到vj的最短路的第一条弧。ijs(n)

=，t则从vi到vj的最短路Floyd算法步骤：=

j

(

i

=

1,2,...,

n;

j

=

1,2,...,

n)s(0)=

(

s(0)

)

,第1步：U

(0)

=

US

(0)ij

n·n

ij第2步：计算(

k

=

1,2,3,...,

n)(

k

=

1,2,3,...,

n)n·nijn·nijS

(

k

)

=

(

s

(

k

)

)U

(

k

)

=

(

u(

k

)

)其中=

min{u}u

(k

-1)

>

u

(k

-1)

+

u

(k

-1)ij

ik

k

j当

u

(k

-1)

£

u

(k

-1)

+

u(k

-1)ij

ik

kj+

uijij

s

(k

-1)(k-1

)kj(k

-1)ik(k

-1)ij(

k

)ij,

uuiks

(k

-1)s

(k)

=

S(n)

=(s(n)

)ij

n·n,ij

n·nU(n)

=(u(n)

)第3步：当k=n时，(

n)ijs是vi到vj最短路第一条弧的终点。是vi到vj最短路路长。(n

)iju例求如下网络中各点对间最短路的路长。v22-3v544v3v1v4-2658解：¥

¥0

4

42

0

6

¥

-3¥

0

¥¥

8

0¥

¥

-2

0

5

¥

¥ ¥

U(0)

=

¥51515511

2

3

4

52

3

42

3

42

3

42

3

4S(0)

=

1用U(0)的第一行、第一列来修正其余的uij，即作{}(0)1

j(0)i

1(0)ij=

miniju(1)+

u,

uumin{¥

，4+5}(1)ij(0)i

1(1)i

j=

SS51¥

¥0

4

42

0

6

¥

-3¥

0

¥¥

8

0¥

¥

-2同时，在修正

u

处修改

0

5

¥

¥ ¥

U(0)

=

¥¥

¥

4

42

0

5

¥

¥

¥

0

6

¥

-3¥

0

¥9

8

09

¥

-2U(1)

=

¥41)

=

s(0)

=

10

1

2

3

4

5

2

3

4

S(1)

=

1

2

3

4

51

1

3

4

51

1

3

4

5与v4到v1的第一段弧相(0)同S11=

12223334445

s(142551234512345用U（1）的第二行、第二列修正其余的uij，

¥0

42

¥

¥

0

¥9

8

09

¥

-2

0

5

¥

¥

¥

0

6

¥

-3U(1)

=

¥

41

2

3

4

51

2

3

4

5

2

3

4

51

1

3

4

51

1

3

4

5S(1)

=

1

¥

46

42

0

5

11

¥

2

0

6

¥

-3¥

0

¥9

8

09

15

-2U(2)

=

¥1

2viv1v

2S(2)

=

1

12v1213

12=

2s(

2)

=

s(1)0

22

43

4

5j3

4

51

1

3

4

11

1

4

5与v

到v1

2的第一段弧相同

¥6

42

-3

0

5

11

¥

2

0

6

¥¥

0

¥U(2)

=

¥5111551

9

8

0

4

9

15

-2 0

1

2

2

4

22

3

42

3

41

3

41

1

4S(2)

=

1用U(2)第三行、第三列修正其余的uij

¥6

42

0

5

11

¥

2

0

6

¥

-3¥

0

¥9

8

09

15

-2U(3)

=

¥5111551

4 0

1

2

2

4

22

3

42

3

41

3

41

1

4S(3)

=

15111551S(3)

=

1

¥0

9

15

-21

2

2

4

22

3

42

3

41

3

41

1

4

46

42

0

5

11

¥

2

0

6

¥

-3¥

0

¥9

8

0U(3)

=

¥用U(3)第四行、第四列修正其余的uij6

2

-32

2

4

¥

0U(4)

=

¥511¥06¥¥0¥98076-251550

21411S(4)

=

122423423413444454(4)

(3)51=

s

=

4s

¥

26

42

0

5

11

¥

2

0

6

¥

-3¥

0

¥9

8

07

6

-2

0U(4)

=

¥11=

12222334442551134144445S(4)用U(4)第五行、第五列修正其余的uij6

2

-32

58003-590098076-22

4-1

0U(5)

=

451550

2412222555351344441(4)15(5)13=

2=

ss(4)35(5)31=

5=

ssS(5)

=

5

51

3从v

到v

的最短路长度从v5到v2的最短路长度u(5)

=

70

26

42

0

5

8

0 2

-1

0

3

-5

-39

0

09

8

07

6

-2U(5)

=

454u(5)

=8

。131555521

2

2

22

55

3

51

44

4

4S(5)

=

513s路径：∵s(5)=

2,

s13∴v1到v3的最短路路经为:P13=P(v1,v2,v5,v4,v3)路径：∵(5)(5)

(5)52

42

1252=

4,

s

=

1,

s

=

2,s∴v5到v2的最短路路经为:P52=P(v5,v4,v1,v2)=

5,(5)23=

4,(5)53=

3(5)43sv1v

v2

5v4v3v5v3v4v253436v1-

412-2U(5)=0

4

5

3

82

0

3

1

6-1

-1

0

-2

3

S(5)=1

2

3

3

33

2

3

3

35

4

3

4

53140722242-401-1011115练习：求各点间最短路径及长度四、Ford算法算法思想：逐次逼近每次逼近是求D中从顶点V1到其余各点的带有限制的最短路。第一次：自顶点到vj由一条弧组成的路中找一条最短的第二次：自顶点到vj由不多于两条弧组成的路中找一条最短的第m次：自顶点到vj由不多于m条弧组成的路中找一条最短的最多进行n-1次逼近定理：设网络D不含负回路，pj(m)是D的自顶点v1到顶点vj由不多于m条弧组成的路中长度最小者，w(pj(m))=uj(m)，j=2,3,…,n,则对于一切2£j

£