大学精品课件：第八章 图论（第4节）.ppt

1、第第1页页1.赋权有向图赋权有向图 给一个有向图给一个有向图 D=(V,A)，对，对 D 中的每一条弧中的每一条弧(vi,vj)，相应地给一个数，相应地给一个数 wij，称，称 wij 为弧上的权，称这为弧上的权，称这样的图样的图 D 为赋权有向图。为赋权有向图。第第2页页v4v1v3v2v5v8v7v66312216104103622第第3页页 2.路权路权在赋权有向图在赋权有向图 D 中，给定两个顶点中，给定两个顶点 vs和和 vn，设，设P是是 D 中从中从 vs 到到 vn 的一条路，定义路的一条路，定义路 P 的权是的权是 P 中所有弧的权之和，记为中所有弧的权之和，记为 w(P)。

2、第第4页页v4v1v3v2v5v8v7v66312216104103622此路的权值此路的权值=3+2+1+6=12此路的权值此路的权值=1+10+2+2=15第第5页页 3.最短路问题最短路问题在赋权有向图在赋权有向图D中，给定两个顶点中，给定两个顶点 vs和和 vn，求出所，求出所有从有从 vs 到到 vn 的路中，权值最小的路的路中，权值最小的路 P0，即，即)(min)(0PwPwP。该问题称为最短路问题。该问题称为最短路问题。路路 P0 的权称为从的权称为从 vs 到到 vn 的距离，记为的距离，记为 d(vs,vn)。注意：注意：d(vs,vn)与与 d(vn,vs)不一定相等。不

3、一定相等。第第6页页 4.最短路问题的意义最短路问题的意义最短路问题是重要的最优化问题之一。它可以直接最短路问题是重要的最优化问题之一。它可以直接应用于解决生产实际中的许多问题，如管道铺设问应用于解决生产实际中的许多问题，如管道铺设问题、线路安排问题、厂区布局问题、设备更新问题题、线路安排问题、厂区布局问题、设备更新问题等。等。第第7页页 5.最短路问题的求解方法最短路问题的求解方法如果最短路能够整齐地划分为若干阶段：用动态规如果最短路能够整齐地划分为若干阶段：用动态规划方法；划方法；如果最短路不能整齐地划分为若干阶段：用图论方如果最短路不能整齐地划分为若干阶段：用图论方法。法。下面介绍二种图

4、论方法，求解最短路问题。下面介绍二种图论方法，求解最短路问题。注意：本节主要以有向图为例，其算法对于无向图注意：本节主要以有向图为例，其算法对于无向图仍然适用。仍然适用。第第8页页1.Dijkstra算法算法（1）适合范围）适合范围适合于图适合于图 D 中，所有弧的权中，所有弧的权 wij0的情况。的情况。该算法是由该算法是由 Dijkstra 于于1959年提出的，当所有弧的年提出的，当所有弧的权权 wij 0时，该算法是公认的最好算法。时，该算法是公认的最好算法。第第9页页（2）基本原理）基本原理若序列若序列 vs,vn-1,vn 是从是从 vs 到到 vn 的最短路，则序的最短路，则序列

5、列 vs,vn-1 必是从必是从 vs 到到 vn-1 的最短路。的最短路。（3）算法步骤）算法步骤Dijkstra算法的步骤采用了为各顶点标号的方式。算法的步骤采用了为各顶点标号的方式。在标号过程中，使用了两种标号：在标号过程中，使用了两种标号：第第10页页T 标号：试探性标号（标号：试探性标号（tentative label）。给一个）。给一个顶点顶点 vi 以以 T 标号时，表示从标号时，表示从 vs 到到 vi 点的估计最短点的估计最短路权，是一种临时标号，路权，是一种临时标号，vi 的的 T 标号随时等待着标号随时等待着变为变为 P 标号。标号。第第11页页P 标号：永久性标号（标号

6、：永久性标号（permanent label）。给一个）。给一个顶点顶点 vi 以以 P 标号时，表示从标号时，表示从 vs 到到 vi 点的最短路权，点的最短路权，vi 的标号不再改变。的标号不再改变。第第12页页算法步骤：算法步骤：给起点给起点 vs 以以 P 标号，且标号，且 P(vs)=0；其余各点均给；其余各点均给 T 标号，且标号，且 T(vi)=+。若若 vi 为刚得到为刚得到 P 标号的点，寻找这样的顶点标号的点，寻找这样的顶点 vj：(vi,vj)组成关联弧，且组成关联弧，且 vj 标号为标号为 T 标号；对标号；对 vj 的的T 标号进行如下更改：标号进行如下更改：)(),

7、(min)(ijijjwvPvTvT 并转步骤并转步骤 。注：如无满足要求的顶点注：如无满足要求的顶点 vj，则直接转步骤，则直接转步骤。第第13页页 比较所有具有比较所有具有 T 标号的顶点，把最小者改为标号的顶点，把最小者改为 P 标号，即标号，即)(min)(iivTvP 并返回步骤并返回步骤 。注：若存在两个以上最小者时，可同时改为注：若存在两个以上最小者时，可同时改为 P 标号。标号。若全部点均为若全部点均为 P 标号，则停止。从而得到从出标号，则停止。从而得到从出发顶点到达图中其他各点的最短路。发顶点到达图中其他各点的最短路。第第14页页例：求从例：求从 v1 到到 v8 的最短路

8、。的最短路。v4v1v3v2v5v8v7v66312216104103622第第15页页v4v1v3v2v5v8v7v66312216104103622解：解：0+min+,0+6=6,v13,v11,v111,v45,v36,v210,v59,v512,v511,v7第第16页页（1）P(v1)=0，T(vi)=+（i=2,9）（2）存在弧）存在弧(v1,v2)、(v1,v3)和和(v1,v4)，且，且v2、v3、v4为为 T 标号标号 T(v2)=min T(v2),P(v1)+w12 =min+,0+6=6 T(v3)=min T(v3),P(v1)+w13 =min+,0+3=3 T(

9、v4)=min T(v4),P(v1)+w14 =min+,0+1=1 第第17页页（3）所有）所有 T 标号中，标号中，T(v4)最小，故最小，故P(v4)=1，并记，并记录路径录路径(v1,v4)（4）存在弧）存在弧(v4,v6)，且，且 v6 为为 T 标号标号 T(v6)=min T(v6),P(v4)+w46=min+,1+10=11（5）所有）所有 T 标号中，标号中，T(v3)最小，故最小，故P(v3)=3，并记，并记录路径录路径(v1,v3)（6）存在弧）存在弧(v3,v2)，且，且 v2 为为 T 标号标号 T(v2)=minT(v2),P(v3)+w32=min6,3+2=

10、5（7）所有）所有 T 标号中，标号中，T(v5)最小，故最小，故P(v2)=5，并记，并记录路径录路径(v3,v2)第第18页页（8）存在弧）存在弧(v2,v5)，且，且 v5 为为 T 标号标号 T(v5)=minT(v5),P(v2)+w25=min+,5+1=6（9）所有）所有 T 标号中，标号中，T(v5)最小，故最小，故P(v5)=6，并记，并记录路径录路径(v2,v5)（10）存在弧）存在弧(v5,v6)、(v5,v7)和和(v5,v8)，且，且v6、v7、v8为为 T 标号标号 T(v6)=minT(v6),P(v5)+w56=min11,6+4=10 T(v7)=minT(v

11、7),P(v5)+w57=min+,6+3=9 T(v8)=minT(v8),P(v5)+w58=min+,6+6=12 第第19页页（11）所有）所有 T 标号中，标号中，T(v7)最小，故最小，故P(v7)=9，并记，并记录路径录路径(v5,v7)（12）存在弧）存在弧(v7,v8)，且，且 v8 为为 T 标号标号 T(v8)=minT(v8),P(v7)+w78=min12,9+2=11（13）所有）所有 T 标号中，标号中，T(v6)最小，故最小，故P(v6)=10，并记，并记录路径录路径(v5,v6)（14）从）从 v6 出发，无法找到满足要求的顶点。出发，无法找到满足要求的顶点。

12、（15）所有）所有 T 标号中，标号中，T(v8)最小，故最小，故 P(v8)=11，并，并记录路径记录路径(v7,v8)（16）全部顶点均为）全部顶点均为 P 标号，停止。标号，停止。从从 v1 到到 v8 的最短路为的最短路为(v1,v3,v2,v5,v7,v8)，距离为，距离为11。第第20页页v4v1v3v2v5v8v7v66312216104103622第第21页页2.逐次逼近算法逐次逼近算法（1）适合范围）适合范围适合于图适合于图 D 中，存在负权弧的情况，即存在中，存在负权弧的情况，即存在wij0的的情况。情况。（2）基本原理）基本原理从从 vs 到到 vj 的最短路总是从的最短

13、路总是从 vs 出发，沿着一条路出发，沿着一条路 P 到到 vi 后，再沿后，再沿(vi,vj)到到vj，则从，则从 vs 到到 vi 的这条路的这条路 P 必必定是从定是从 vs 到到 vi 的最短路。的最短路。第第22页页所以，所以，d(vs,vj)必须满足如下方程：必须满足如下方程：),(min),(ijisijswvvdvvd （3）算法步骤）算法步骤)(,.,2,1(),()1(Dpjwvvdsjjs ,.)3,2);(,.,2,1(),(min),()1()(tDpjwvvdvvdijistijst第第23页页 当当 t=k 时，对所有时，对所有 j=1,2,p(D)满足：满足：)

14、,(),()1()(jskjskvvdvvd 停止跌代，停止跌代，)(,.,2,1),()(Dpjvvdjsk，则即从，则即从 vs 为到各点的最短路。为到各点的最短路。第第24页页例：求从例：求从 v1 到各点的最短路。到各点的最短路。v4v1v3v2v5v8v76-18-5-3-1127-3-5-23v6211-1第第25页页解：解：（1）d(1)(v1,v1)=0 ，d(1)(v1,v5)=+d(1)(v1,v2)=-1 ，d(1)(v1,v6)=+d(1)(v1,v3)=-2 ，d(1)(v1,v7)=+d(1)(v1,v4)=3 ，d(1)(v1,v8)=+v4v1v3v2v5v8v

15、76-18-5-3-1127-3-5-23v6211-1第第26页页d(2)(v1,v1)=000),(1111)1(wvvd),(21)2(vvd),(32vvv4v1v3v2v5v8v76-18-5-3-1127-3-5-23v6211-15)1(),(5)3(2),(010),(min5251)1(3231)1(1211)1(wvvdwvvdwvvd（2）第第27页页2)2(0),(),(1311)1(31)2(wvvdvvd),(31vv77)1(),(7)5(2),(330),(min),(7471)1(3431)1(1411)1(41)2(wvvdwvvdwvvdvvd),(43v

16、vv4v1v3v2v5v8v76-18-5-3-1127-3-5-23v6211-1第第28页页1)3(),(1),(121),(min),(8581)1(6561)1(2521)1(51)2(wvvdwvvdwvvdvvd),(52vv112),(),(3631)1(61)2(wvvdvvd),(63vvv4v1v3v2v5v8v76-18-5-3-1127-3-5-23v6211-1第第29页页5)5(),(1),(523),(min),(8781)1(6761)1(4741)1(71)2(wvvdwvvdwvvdvvd),(74vv 7),(),(6861)1(81)2(wvvdvvd)

17、,(86vvv4v1v3v2v5v8v76-18-5-3-1127-3-5-23v6211-1第第30页页000),(),(1111)2(11)3(wvvdvvd50)1(1),(5)3(2),(010),(min),(5251)2(3231)2(1211)2(21)3(wvvdwvvdwvvdvvd（3）2)2(0),(),(1311)2(31)3(wvvdvvd),(23vv),(31vv第第31页页74)1(5),(7)5(2),(330),(min),(7471)2(3431)2(1411)2(41)3(wvvdwvvdwvvdvvd),(43vv3)3(),(011),(325),(

18、min),(8581)2(6561)2(2521)2(51)3(wvvdwvvdwvvdvvd),(52vv第第32页页112),(),(3631)2(61)3(wvvdvvd),(63vv5)5(),(011),(527),(min),(8781)2(6761)2(4741)2(71)3(wvvdwvvdwvvdvvd),(74vv671),(),(6861)2(81)3(wvvdvvd),(86vv第第33页页（4）000),(),(1111)3(11)4(wvvdvvd54)1(3),(5)3(2),(010),(min),(5251)3(3231)3(1211)3(21)4(wvvdw

19、vvdwvvdvvd),(23vv2)2(0),(),(1311)3(31)4(wvvdvvd),(31vv第第34页页76)1(5),(7)5(2),(330),(min),(7471)3(3431)3(1411)3(41)4(wvvdwvvdwvvdvvd),(43vv33)3(6),(011),(325),(min),(8581)3(6561)3(2521)3(51)4(wvvdwvvdwvvdvvd),(52vv第第35页页51)5(6),(011),(527),(min),(8781)3(6761)3(4741)3(71)4(wvvdwvvdwvvdvvd),(74vv112),()

20、,(3631)3(61)4(wvvdvvd),(63vv第第36页页671),(),(6861)3(81)4(wvvdvvd),(86vv停止。停止。v1 到到 v8 的最短路径为的最短路径为(v1,v3,v6,v8)，路权为，路权为 6。第第37页页wij d(t)(v1,vj)v1 v2v3v4v5v6v7v8t=1 t=2 t=3 t=4 v10-1-230000v2602-1-5-5-5v3-30-51-2-2-2-2v4023-7-7-7v5-101-3-3v61017-1-1-1v7-105-5-5v8-3-5066第第38页页3.Floyd 算法算法（1）适合范围）适合范围Dij

21、kstra法和逐次逼近法适合于从适合于从某一点法和逐次逼近法适合于从适合于从某一点出发，到达各点的最短路。出发，到达各点的最短路。Floyd 算法适合于求图算法适合于求图 D 中任意两点的最短路。中任意两点的最短路。第第39页页（2）算法步骤）算法步骤令图的权矩阵为令图的权矩阵为 D=(dij)nn，lij 为为 vi 到到 vj 的距离，的距离，其中其中 ，其其他他，Evvldjiijij),(第第40页页输入权矩阵输入权矩阵 D(0)=D。计算计算 ，中元素就是中元素就是 vi 到到 vj 的最短路长的最短路长nnnijkdD )()()(,min)1()1()1()(kkjkikkijk

22、ijddddnnnijndD )()()(第第41页页例：求图中任意两点间的最短路。例：求图中任意两点间的最短路。v52v4v1v2v3524621231084第第42页页解：图中既有边，也有弧。将边化为两条方向相反的弧。解：图中既有边，也有弧。将边化为两条方向相反的弧。v52v4v1v2v352462123108455224422第第43页页 55545352514544434241353433323125242322211514131211)0(0442406282032210052150DD,min)0(1)0(1)0()1(jiijijdddd )1(D1151141131121112

23、150 21521421321221176105 3153143133123114372 4154144134124114372 515514513512511 对两矩阵中对两矩阵中所有元素一所有元素一一比较，取一比较，取较小元素较小元素 555453525145444342413534333231252423222115141312110442406282032210052150 55545352514544413412413534333231252142132221151413121104424037282032276052150第第44页页,min)1(2)1(2)1()2(jiijij

24、dddd )2(D1251241231221217121151022522422322222127605325324323322321510938412541244123412241219141371252552452352252149827对两矩阵中对两矩阵中所有元素一所有元素一一比较，取一比较，取较小元素较小元素 555453525145444134124135343332312521421322211514131211)1(04424037282032276052150D 5554535251454441341241353433323125214213222115141312110442

25、4037282032276052150 5554535252145444134124132534333231252142132221125141312110442740372520322760572150第第45页页,min)2(3)2(3)2()3(jiijijdddd )3(D132513413313213163143213252134213213221311186983325334333332331520324132541344133413241318536553255345353253196476对两矩阵中对两矩阵中所有元素一所有元素一一比较，取一比较，取较小元素较小元素 555453

26、525214544413412413253433323125214213222112514131211)2(0442740372520322760572150D 5554535252145444134124132534333231252142132221125141312110442740372520322760572150 5554535253145444134132413253433323125214213222113251413132120442640362520322760562140第第46页页,min)3(4)3(4)3()4(jiijijdddd )4(D145141413141

27、3214162584214521421413214132214111710139345343413341323416258445444134132414036254554541354132541847106对两矩阵对两矩阵中所有元中所有元素一一比素一一比较，取较较，取较小元素小元素 555453525314544413413241325343332312521421322211325141313212)3(0442640362520322760562140D 55545352531454441341324132534333231252142132221132514131321204426403

28、62520322760562140 5554535253145444134132413253433323125214213222113251413132120442640362520322760562140第第47页页,min)4(5)4(5)4()5(jiijijdddd )5(D132513254132531325213253161010812252542532522531266483253254325332523253159971145454453452453148861055545352531847106对两矩对两矩阵中所阵中所有元素有元素一一比一一比较，取较，取较小元较小元素素 55

29、5453525314544413413241325343332312521421322211325141313212)4(0442640362520322760562140D 5554535253145444134132413253433323125214213222113251413132120442640362520322760562140 5554535253143424134132413253433323125254213222113251413132120442640362520322660562140第第48页页 5554535253143424134132413253433323

30、125254213222113251413132120442640362520322660562140第第49页页例例 某工厂使用一台设备，每年年初工厂都要作出决某工厂使用一台设备，每年年初工厂都要作出决定，如果继续使用旧的，要付维修费；若购买一台定，如果继续使用旧的，要付维修费；若购买一台新设备，要付购买费。试制定一个新设备，要付购买费。试制定一个 5 年更新计划，年更新计划，使总支出最少。使总支出最少。若已知设备在各年的购买费，及不同机器役龄时的若已知设备在各年的购买费，及不同机器役龄时的残值与维修费如下表所示。残值与维修费如下表所示。第第50页页项目项目第第 1 年年第第 2 年年第第

31、3 年年第第 4 年年第第 5 年年购买费购买费1112131414机器役龄机器役龄0-11-22-33-44-5维修费维修费5681118残值残值43210第第51页页解：把这个问题化为最短路问题。解：把这个问题化为最短路问题。点点 vi：表示第：表示第 i 年年初购进一台新设备。虚设一个点年年初购进一台新设备。虚设一个点 v6 表示第表示第 5 年年底。年年底。弧弧(vi,vj)：表示第：表示第 i 年年初购进的设备一直使用到第年年初购进的设备一直使用到第 j 年年初。年年初。弧弧(vi,vj)上的数字：表示第上的数字：表示第 i 年年初购进设备，一直年年初购进设备，一直使用到第使用到第

32、j 年年初所需支付的购买、维修总费用。年年初所需支付的购买、维修总费用。第第52页页购买费购买费分分 析析购买费购买费维修费维修费残值残值总费用总费用(v1,v2)第第 1 年买，使用年买，使用 1 年年115412(v1,v3)第第 1 年买，使用年买，使用 2 年年115+6319(v1,v4)第第 1 年买，使用年买，使用 3 年年115+6+8228(v1,v5)第第 1 年买，使用年买，使用 4 年年115+6+8+11140(v1,v6)第第 1 年买，使用年买，使用 5 年年115+6+8+11+18059第第 1 年购买年购买 1 台设备，分别使用台设备，分别使用 1、2、3、

33、4、5年的费用年的费用第第53页页购买费购买费分分 析析购买费购买费维修费维修费残值残值总费用总费用(v2,v3)第第 2 年买，使用年买，使用 1 年年125413(v2,v4)第第 2 年买，使用年买，使用 2 年年125+6320(v2,v5)第第 2 年买，使用年买，使用 3 年年125+6+8229(v2,v6)第第 2 年买，使用年买，使用 4 年年125+6+8+11141第第 2 年购买年购买 1 台设备，分别使用台设备，分别使用 1、2、3、4 年的费用年的费用第第54页页购买费购买费分分 析析购买费购买费维修费维修费残值残值总费用总费用(v3,v4)第第 3 年买，使用年买

34、，使用 1 年年135414(v3,v5)第第 3 年买，使用年买，使用 2 年年135+6321(v3,v6)第第 3 年买，使用年买，使用 3 年年135+6+8230第第 3 年购买年购买 1 台设备，分别使用台设备，分别使用 1、2、3年的费用年的费用第第55页页购买费购买费分分 析析购买费购买费维修费维修费残值残值总费用总费用(v4,v5)第第 4 年买，使用年买，使用 1 年年145415(v4,v6)第第 4 年买，使用年买，使用 2 年年145+6322第第 4 年购买年购买 1 台设备，分别使用台设备，分别使用 1、2年的费用年的费用购买费购买费分分 析析购买费购买费维修费维

35、修费残值残值总费用总费用(v5,v6)第第 5 年买，使用年买，使用 1 年年145415第第 5 年购买年购买 1 台设备，使用台设备，使用 1 年的费用年的费用第第56页页1213141515v1v2v3v4v5v619284059202941213022第第57页页从而设备更新问题变为：求从从而设备更新问题变为：求从 v1 到到 v6 的最短路问的最短路问题，计算结果表明：题，计算结果表明：v1、v3、v6为最短路，路长为为最短路，路长为49。即，在第一年、第三年年初各购买一台设备为最优即，在第一年、第三年年初各购买一台设备为最优策略，这时的总费用为策略，这时的总费用为 49。第第58页

36、页例例 已知某地区的交通网络如图所示，其中点代表居已知某地区的交通网络如图所示，其中点代表居民小区，边表示公路，民小区，边表示公路，lij 表示小区间的公路距离，表示小区间的公路距离，问区中心医院应建在哪个小区，可使离医院最远的问区中心医院应建在哪个小区，可使离医院最远的小区居民就诊时所走的路程最近？小区居民就诊时所走的路程最近？v1v2v6v3v4v5v7603020182520153015第第59页页解：解：（1）利用）利用 Dijkstra 算法求算法求 v1 到其他各点的最短路到其他各点的最短路dj，并找出其中的最大值，并找出其中的最大值 D(v1)=max d1,d7；（2）按相同的方法依次求解）按相同的方法依次求解 v2，v7到其余各点到其余各点的最短路，并求出的最短路，并求出 D(v2),D(v7)；（3）比较）比较D(v1),D(v7)中的最小者，即为所求。中的最小者，即为所求。