熊伟编《运筹学》Ch6网络模型

1、2021-10-14 运运 筹筹 学学 Operations Research Chapter 6 网络模型网络模型Network Modeling6.1 最小最小(支撑支撑)树问题树问题 Minimal (Spanning)Tree Problem6.2 最短路问题最短路问题 Shortest Path Problem 6.3 最大流问题最大流问题 Maximal Flow Problem6.4 旅行售货员与中国邮路问题旅行售货员与中国邮路问题 Traveling Salesman and China Carrier Problem Ch6 网络模型网络模型 Network Model Pa

2、ge 2 2021-10-14 哥尼斯堡七桥问题 CDABABCD因为图因为图 2 2中的每个点都只与奇数条线相关联中的每个点都只与奇数条线相关联, ,不不可能将这个图不重复地一笔画成。可能将这个图不重复地一笔画成。 Ch6 网络模型网络模型 Network Model Page 3 2021-10-14 点和线画出各种各样的示意图 此图反映了这七个城市间的铁路分布情况。这里用点代表城市,用点和点之间的联线代表这两个城市之间的铁路线。诸如此类的还有 线分布图,煤气管道图,航空线图等等 北京郑州 武汉 济南 徐州 南京 天津Ch6 网络模型网络模型 Network Model Page 4 20

3、21-10-14例例2,2,有甲有甲, ,乙乙, ,丙丙, ,丁丁, ,戊五个球队戊五个球队, ,它们之间比赛的情况它们之间比赛的情况, ,也可以用图表也可以用图表示出来示出来。已知甲队和其它各队都比赛过一次已知甲队和其它各队都比赛过一次, ,乙队和甲丙队比赛过乙队和甲丙队比赛过, ,丙丙队和乙队和乙, ,丁队比赛过丁队比赛过, ,丁队和丙丁队和丙, ,戊队比赛过戊队比赛过, ,戊队和甲戊队和甲, ,丁队比赛过丁队比赛过。 为了反映这个情况为了反映这个情况, ,可以用点可以用点v v1 1, v, v2 2, v, v3 3, v, v4 4, v, v5 5分别代表这五个队分别代表这五个队,

4、 ,某两个队之间比赛过某两个队之间比赛过, ,就在这两个队所相应的点之间联一条线就在这两个队所相应的点之间联一条线, ,这条线这条线不过其它的点不过其它的点, ,如图所示如图所示 v v1 1V V2 2V V3 3V V4 4V V5 5图4V1V2V5V4V3图5Ch6 网络模型网络模型 Network Model Page 5 2021-10-145v1v2v3v4v5v6843752618图图61运筹学中研究的图具有下列特征：运筹学中研究的图具有下列特征：（1）用点表示研究对象，用边（有方向或无方向）表示对）用点表示研究对象，用边（有方向或无方向）表示对象之间某种关系。象之间某种关系。

5、（2）强调点与点之间的关联关系，不讲究图的比例大小与）强调点与点之间的关联关系，不讲究图的比例大小与形状。形状。（3）每条边上都赋有一个权，其图称为赋权图。实际中权）每条边上都赋有一个权，其图称为赋权图。实际中权可以代表两点之间的距离、费用、利润、时间、容量等不同的可以代表两点之间的距离、费用、利润、时间、容量等不同的含义。含义。（4）建立一个网络模型，求最大值或最小值。）建立一个网络模型，求最大值或最小值。Ch6 网络模型网络模型 Network Model Page 6 2021-10-14图的意义图的意义 因此因此, ,可以说图是反映对象之间关系的一种工可以说图是反映对象之间关系的一种工

6、具具, ,在一般情况下在一般情况下, ,图中点的相对位置如何图中点的相对位置如何, ,点与点点与点之间联线的长短曲直之间联线的长短曲直, ,对于反映对象之间的关系对于反映对象之间的关系, ,并不是重要的并不是重要的。 如例如例2,2,也可以用如图也可以用如图4 4所示的图去反映五个球队所示的图去反映五个球队的比赛情况的比赛情况, ,这与图这与图5 5没有本质的区别没有本质的区别, ,所以所以, ,图论图论中的图与几何图中的图与几何图, ,工程图等是不同的工程图等是不同的. . Ch6 网络模型网络模型 Network Model Page 7 2021-10-14 用用G=G=（V V，E E

7、） 表示表示 其中其中V V表示图表示图G G的全部顶点的集合的全部顶点的集合 E E表示图表示图G G的全部边的集合的全部边的集合 v图由点和边组成图由点和边组成q 图的基本概念图的基本概念例如：例如：V=V=（v v1 1, v, v2 2, v, v3 3，v v4 4, v, v5 5, , v v6 6 ），），E=E=（e e1 1, e, e2 2, e, e3 3, e, e4 4, , e e5 5, e, e6 6, e, e6 6, , ）边与点间的关）边与点间的关联情况如下：联情况如下：e e4 4e e2 2v v1 1V V2 2V V3 3V V4 4V V5 5

8、V V6 6e e1 1e e3 3e e5 5e e6 6e e7 7q 无向图无向图q 有向图有向图Ch6 网络模型网络模型 Network Model Page 8 2021-10-14126,Vv vv边用边用vi,vj表示或简记为表示或简记为i，j，集合记为，集合记为如图如图61所示，点集合记为所示，点集合记为12,13,5 6E，边上的数字称为权，记为边上的数字称为权，记为wvi,vj、wi，j或或wij，集合记为，集合记为12131456,Wwwww连通的赋权图称为网络图，记为连通的赋权图称为网络图，记为 GV，E，W5v1v2v3v4v5v6843752618图图61Ch6 网

9、络模型网络模型 Network Model Page 9 2021-10-14v 点与边点与边 每一条边和两个节点关联，一条边可以用每一条边和两个节点关联，一条边可以用两个节点的标号表示（两个节点的标号表示（i，j）jiv链（链（Path） 前后相继的点边序列前后相继的点边序列 P=(1,2),(2,3),(3,4)4231无向图中的基本概念4231Ch6 网络模型网络模型 Network Model Page 10 2021-10-14v圈圈(Cycle) 起点和终点重合的链称为起点和终点重合的链称为圈圈 =(1,2),(2,4),(4,3),(3,1) 圈中各条边方向不一定相同圈中各条边方

10、向不一定相同4231Ch6 网络模型网络模型 Network Model Page 11 2021-10-14v 点与弧（有向边点与弧（有向边) 每一条弧和两个节点关联，一条弧可以用每一条弧和两个节点关联，一条弧可以用两个节点的标号表示（两个节点的标号表示（i，j）jiv路径（路径（Path） 前后相继并且方向相同的弧序列前后相继并且方向相同的弧序列 P=(1,3),(3,2),(2,4)42314231有向图中的基本概念Ch6 网络模型网络模型 Network Model Page 12 2021-10-14v 回路（回路（Circuit） 起点和终点重合的路径称为起点和终点重合的路径称为回

11、路回路 =(1,2),(2,4),(4,1) 回路中各条边方向相同回路中各条边方向相同4231v 链（链（Chain） 前后相继并且方向不一定相同的边序前后相继并且方向不一定相同的边序列称为列称为链链 C=(1,2),(3,2),(3,4)4231有向图中的基本概念2021-10-146.1 最小最小(支撑支撑)树问题树问题 Minimal (Spanning)Tree ProblemCh6 网络模型网络模型 Network Model Page 14 2021-10-144231v子图子图 设G=(V,E)是一个图,若VV1,EE,且(V,E)是图,则称G=(V,E)是G的一个子图子图 v生

12、成子图生成子图满足条件V= V的子图称为G的生成生成子图子图. . 2314231Ch6 网络模型网络模型 Network Model Page 15 2021-10-14v连通图连通图 任意两个节点之间至少有一条任意两个节点之间至少有一条链的图称为链的图称为连通图连通图24351v树树(Tree) 无圈的连通图称为树无圈的连通图称为树 树中只与一条边关联的节点称树中只与一条边关联的节点称为为悬挂节点悬挂节点4231Ch6 网络模型网络模型 Network Model Page 16 2021-10-14 树树 的的 性性 质质任何树至少有一个悬挂节点任何树至少有一个悬挂节点243512435

13、124351v如果树的节点个数为如果树的节点个数为m，则边的个，则边的个数为数为m-1v树中任意两个节点之间只有唯一树中任意两个节点之间只有唯一的一条链的一条链v在树的任意两个不相邻的节点之在树的任意两个不相邻的节点之间增加一条边，则形成唯一的圈间增加一条边，则形成唯一的圈Ch6 网络模型网络模型 Network Model Page 17 2021-10-14树的概念树的概念 一个无圈并且连通的无向图称为树图或简称树一个无圈并且连通的无向图称为树图或简称树(Tree)。组织机。组织机构、家谱、学科分支、因特网络、通讯网络及高压线路网络等构、家谱、学科分支、因特网络、通讯网络及高压线路网络等都

14、能表达成一个树图都能表达成一个树图 。 可以证明：可以证明：（1）一棵树的边数等于点数减）一棵树的边数等于点数减1；（2）在树中任意两个点之间添加一条边就形成圈；）在树中任意两个点之间添加一条边就形成圈；（3）在树中去掉任意一条边图就变为不连通。）在树中去掉任意一条边图就变为不连通。 在一个连通图在一个连通图G中，中，取部分边连接取部分边连接G的所的所有点组成的树称为有点组成的树称为G的的部分树部分树或或支撑树支撑树(Spanning Tree )。图图62是图是图61的的部分树。部分树。 v1v2v3v4v5v64321图图6276.1 最小树问题最小树问题 Minimal tree pro

15、blemCh6 网络模型网络模型 Network Model Page 18 2021-10-146.1.2 最小部分树最小部分树将网络图将网络图G边上的权看作两点间的长度（距离、费用、时间），边上的权看作两点间的长度（距离、费用、时间），定义定义G的部分树的部分树T的长度等于的长度等于T中每条边的长度之和，记为中每条边的长度之和，记为C(T)。 G的所有部分树中长度最小的部分树称为的所有部分树中长度最小的部分树称为最小部分树最小部分树，或简称，或简称为为最小树最小树。 最小部分树可以直接用作图的方法求解，常用的有破圈法和最小部分树可以直接用作图的方法求解，常用的有破圈法和加边法。加边法。破圈

16、法破圈法：任取一圈，去掉圈中最长边，直到无圈。：任取一圈，去掉圈中最长边，直到无圈。6.1 最小树问题最小树问题 Minimal tree problemCh6 网络模型网络模型 Network Model Page 19 2021-10-145v1v2v3v4v5v6843752618图图61【例【例6.1】用破圈法求图】用破圈法求图61的最小树。的最小树。 图图64图图64就是图就是图61的最小部分树，最小树长为的最小部分树，最小树长为 C(T)=4+3+5+2+1=15。当一个圈中有多个相同的最长边时，不能同时都去掉，只能去当一个圈中有多个相同的最长边时，不能同时都去掉，只能去掉其中任意

17、一条边。最小部分树有可能不唯一，但最小树的长掉其中任意一条边。最小部分树有可能不唯一，但最小树的长度相同度相同 6.1 最小树问题最小树问题 Minimal tree problemCh6 网络模型网络模型 Network Model Page 20 2021-10-14加边法加边法：取图：取图G的的n个孤立点个孤立点v1，v2， vn作为一个支撑作为一个支撑图，从最短边开始往支撑图中添加，见圈回避，直到连通（有图，从最短边开始往支撑图中添加，见圈回避，直到连通（有n1条边）条边） v1v2v3v4v5v643521图图65在图在图65中，如果添加边中，如果添加边v1, v2就形成圈就形成圈v

18、1, v2, v4，这时就，这时就应避开添加边应避开添加边v1, v2，添加下一条最短边，添加下一条最短边v3, v6。破圈法和加边。破圈法和加边法得到树的形状可能不一样，但最小树的长度相等法得到树的形状可能不一样，但最小树的长度相等 5v1v3v515v2v4v684375268Min C(T)=156.1 最小树问题最小树问题 Minimal tree problemCh6 网络模型网络模型 Network Model Page 21 2021-10-14最小支撑树权值为19例题：5231781454762433265Ch6 网络模型网络模型 Network Model Page 22 2

19、021-10-14最小支撑树权值为19例题：5231781454762433265Ch6 网络模型网络模型 Network Model Page 23 2021-10-14下一节：最短路问题下一节：最短路问题1.树、支撑树、最小支撑树的概念树、支撑树、最小支撑树的概念2.掌握求最小树的方法：掌握求最小树的方法： （1）破圈法）破圈法 （2）加边法）加边法作业：作业：P149 T 1，4，56.1 最小树问题最小树问题 Minimal tree problem2021-10-146.2 最短路问题最短路问题 Shortest Path ProblemCh6 网络模型网络模型 Network Mo

20、del Page 25 2021-10-14237184562421182151124829 现问从现问从u u1 1到到u u8 8, ,的各条路线中的各条路线中, ,哪一条的总长度最短哪一条的总长度最短? ?Ch6 网络模型网络模型 Network Model Page 26 2021-10-14最短路问题在实际中具有广泛的应用，如管道铺设、线路选择最短路问题在实际中具有广泛的应用，如管道铺设、线路选择等问题，还有些如设备更新、投资等问题也可以归结为求最短等问题，还有些如设备更新、投资等问题也可以归结为求最短路问题路问题 求最短路有两种算法：求最短路有两种算法： 一是求从某一点至其它各点之

21、间最短离的一是求从某一点至其它各点之间最短离的狄克斯屈拉狄克斯屈拉(Dijkstra)算法算法 另一种是求网络图上任意两点之间最短路的另一种是求网络图上任意两点之间最短路的Floyd(弗洛伊德弗洛伊德)矩阵算法。矩阵算法。最短路问题，就是从给定的网络图中找出一点到各点或任意两最短路问题，就是从给定的网络图中找出一点到各点或任意两点之间距离最短的一条路点之间距离最短的一条路 最短路问题的网络模型最短路问题的网络模型6.2 最短路问题最短路问题 Shortest Path Problem Ch6 网络模型网络模型 Network Model Page 27 2021-10-146101232146

22、75811165图图669【例【例6.3】图】图66中的权中的权cij表示表示vi到到vj的距离（费用、时间），从的距离（费用、时间），从v1修一条公路或架设一条高压线到修一条公路或架设一条高压线到v7，如何选择一条路线使距离，如何选择一条路线使距离最短，建立该问题的网络数学模型。最短，建立该问题的网络数学模型。6.2 最短路问题最短路问题 Shortest Path Problem Ch6 网络模型网络模型 Network Model Page 28 2021-10-14【解】【解】 设设xij为选择弧为选择弧(i，j)的状态变量，选择弧的状态变量，选择弧(i，j)时时xij1，不，不选择弧

23、选择弧(i，j)时时xij0，得到最短路问题的网络模型：，得到最短路问题的网络模型：( , )12( , )( , )57131467min102,3,610( , )ijiji jEijkii jEk iEijZc xxxxxxixxxi jE或1，6.2 最短路问题最短路问题 Shortest Path Problem Ch6 网络模型网络模型 Network Model Page 29 2021-10-14有向图的狄克斯屈拉有向图的狄克斯屈拉(Dijkstra)标号算法标号算法点标号：点标号：b(j) 起点起点vs到点到点vj的最短路长；的最短路长；边标号：边标号：k(i，j)=b(i)

24、+cij，步骤：步骤：(1)令起点的标号；令起点的标号；b(s)0。先求有向图的最短路，设网络图的起点是先求有向图的最短路，设网络图的起点是vs ,终点是终点是vt ,以以vi为起为起点点vj为终点的弧记为（为终点的弧记为（i，j）,距离为距离为cij (2)找出所有找出所有vi已标号已标号vj未标号的弧集合未标号的弧集合 B=(i，j)，如果这样，如果这样的弧不存在或的弧不存在或vt已标号则计算结束；已标号则计算结束；(3)计算集合计算集合B中弧中弧k(i，j)=b(i)+cij的标号的标号(4)选一个点标号选一个点标号 返回到第返回到第(2)步。步。)(,),( | ),(min)(lbv

25、Bjijiklblj处标号在终点6.2 最短路问题最短路问题 Shortest Path Problem Ch6 网络模型网络模型 Network Model Page 30 2021-10-14610123214675811165图图6690610129209186161217162432182929【例【例6.4】用】用Dijkstra算法求图算法求图66 所示所示v1到到v7的最短路及最短路长的最短路及最短路长 v1 到到v7的最短路为：的最短路为：p17=v1, v2, v3, v5, v7，最短路长为，最短路长为L17=29 6.2 最短路问题最短路问题 Shortest Path

26、Problem 14Ch6 网络模型网络模型 Network Model Page 31 2021-10-14从上例知，只要某点已标号，说明已找到起点从上例知，只要某点已标号，说明已找到起点vs到该点的最短路到该点的最短路线及最短距离，因此可以将每个点标号，求出线及最短距离，因此可以将每个点标号，求出vs到任意点的最短到任意点的最短路线，如果某个点路线，如果某个点vj不能标号，说明不能标号，说明vs不可达不可达vj 。6.2 最短路问题最短路问题 Shortest Path Problem Ch6 网络模型网络模型 Network Model Page 32 2021-10-142371845

27、62421182151124829 现问从现问从u u1 1到到u u8 8, ,的各条路线中的各条路线中, ,哪一条的总长度哪一条的总长度? ?最短路问题最短路问题（0 0，1 1） 8211（2 2，1 1） Ch6 网络模型网络模型 Network Model Page 33 2021-10-14 现问从现问从u u1 1到到u u8 8, ,的各条路线中的各条路线中, ,哪一条的总长度哪一条的总长度? ?（0 0，1 1） 2371845624211821511248298211（2 2，1 1） 67（6 6，3 3） 最短路问题最短路问题Ch6 网络模型网络模型 Network M

28、odel Page 34 2021-10-14 现问从现问从u u1 1到到u u8 8, ,的各条路线中的各条路线中, ,哪一条的总长度哪一条的总长度? ?（0 0，1 1） 2371845624211821511248298211（2 2，1 1） 67（6 6，3 3） 15 （7 7，3 3） 最短路问题最短路问题Ch6 网络模型网络模型 Network Model Page 35 2021-10-14 现问从现问从u u1 1到到u u8 8, ,的各条路线中的各条路线中, ,哪一条的总长度最短哪一条的总长度最短? ?（0 0，1 1） 23718456242118215112482

29、98211（2 2，1 1） 67（6 6，3 3） 15 （7 7，3 3） 811 （8 8，6 6） 15最短路问题最短路问题Ch6 网络模型网络模型 Network Model Page 36 2021-10-14 现问从现问从u u1 1到到u u8 8, ,的各条路线中的各条路线中, ,哪一条的总长度哪一条的总长度? ?（0 0，1 1） 2371845624211821511248298211（2 2，1 1） 67（6 6，3 3） 15 （7 7，3 3） 811 （8 8，6 6） 1520 （1111，6 6） 最短路问题最短路问题Ch6 网络模型网络模型 Network

30、 Model Page 37 2021-10-14 现问从现问从u u1 1到到u u8 8, ,的各条路线中的各条路线中, ,哪一条的总长度哪一条的总长度? ?（0 0，1 1） 2371845624211821511248298211（2 2，1 1） 67（6 6，3 3） 15 （7 7，3 3） 811 （8 8，6 6） 1520 （1111，6 6） 13 （1313，7 7） 从从u u1 1到到u u8 8, ,的最短路为的最短路为13,13,路径为路径为1-3-6-7-81-3-6-7-8最短路问题最短路问题Ch6 网络模型网络模型 Network Model Page 3

31、8 2021-10-14237184562421182151124829 现问从现问从u u1 1到到u u8 8, ,的各条路线中的各条路线中, ,哪一条的总长度哪一条的总长度? ?（0 0，1 1） 8211（2 2，1 1） 67（6 6，3 3） 15 （7 7，3 3） 15118 （8 8，6 6） 20 （1111，6 6） 13 （1313，7 7） 从从u u1 1到到u u8 8, ,的最短路为的最短路为13,13,路径为路径为1-3-6-7-81-3-6-7-8最短路问题最短路问题Ch6 网络模型网络模型 Network Model Page 39 2021-10-142

32、37184566134105275934682求从求从1到到8的最短路径的最短路径 最短路问题练习最短路问题练习Ch6 网络模型网络模型 Network Model Page 40 2021-10-14237184566134105275934682min c12,c14,c16=min 0+2,0+1,0+3=min 2,1,3=1X=1,4, y4=1(1,1)(0,1) 最短路问题练习最短路问题练习Ch6 网络模型网络模型 Network Model Page 41 2021-10-14237184566134105275934682min c12,c16,c42,c47=min 0+2

33、,0+3,1+10,1+2=min 2,3,11,3=2X=1,2,4, y2=2(0,1)(1,1)(2,1) 最短路问题练习最短路问题练习Ch6 网络模型网络模型 Network Model Page 42 2021-10-14237184566134105275934682min c13,c23,c25,c47=min 0+3,2+6,2+5,1+2=min 3,8,7,3=3X=1,2,4,6, y6=3(2,1)(1,1)(0,1)y6=3 最短路问题练习最短路问题练习Ch6 网络模型网络模型 Network Model Page 43 2021-10-142371845661341

34、05275934682min c23,c25,c47,c67=min 2+6,2+5,1+2,3+4=min 8,7,3,7=3X=1,2,4,6,7, y7=3(2,1)(1,1)(0,1)(3,1)y7=3 最短路问题练习最短路问题练习Ch6 网络模型网络模型 Network Model Page 44 2021-10-14237184566134105275934682min 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, y5=6(2,1)(1,1)(0,1)(3,1)(3,4)(6,7) 最短路问题练习

35、最短路问题练习Ch6 网络模型网络模型 Network Model Page 45 2021-10-14237184566134105275934682min c23,c53,c58,c78=min 2+6,6+9,6+4,3+8=min 8,15,10,11=8X=1,2,3,4,5,6,7, y3=8(2,1)(1,1)(0,1)(3,1)(3,4)(6,7)(8,2) 最短路问题练习最短路问题练习Ch6 网络模型网络模型 Network Model Page 46 2021-10-14237184566134105275934682min c38,c58,c78=min 8+6,6+4,

36、3+8=min 14,10,11=10X=1,2,3,4,5,6,7,8, y8=10(2,1)(1,1)(0,1)(3,1)(3,4)(6,7)(8,2)(10,5) 最短路问题练习最短路问题练习Ch6 网络模型网络模型 Network Model Page 47 2021-10-142371845661341052759346821到10的最短路径为1，4，7，5，8，长度为10。(2,1)(1,1)(0,1)(3,1)(3,4)(6,7)(8,2)(10,5) 最短路问题练习最短路问题练习Ch6 网络模型网络模型 Network Model Page 48 2021-10-146.2.3

37、 无向图最短路的求法无向图最短路的求法无向图最短路的求法只将上述步骤（无向图最短路的求法只将上述步骤（2）改动一下即可。）改动一下即可。点标号：点标号：b(i) 起点起点vs到点到点vj的最短路长；的最短路长；边标号：边标号：k(i，j)=b(i)+cij，步骤：步骤：(1)令起点的标号；令起点的标号；b(s)0。(3)计算集合计算集合B中边标号：中边标号：ki，j=b(i)+cij)(, | ,min)(lbvBjijiklblj处标号在端点(4)选一个点标号选一个点标号: 返回到第返回到第(2)步。步。 (2)找出所有一端找出所有一端vi已标号另一端已标号另一端vj未标号的边集合未标号的边

38、集合 B=i，j如如果这样的边不存在或果这样的边不存在或vt已标号则计算结束；已标号则计算结束；6.2 最短路问题最短路问题 Shortest Path Problem Ch6 网络模型网络模型 Network Model Page 49 2021-10-14【例【例6.5】求图】求图6-10所示所示v1到各点的最短路及最短距离到各点的最短路及最短距离4526178393261216180452231039612641166188122482418所有点都已标号，点上的标号就是所有点都已标号，点上的标号就是v1到该点的最短距离，最短路到该点的最短距离，最短路线就是红色的链。线就是红色的链。图图

39、6-106.2 最短路问题最短路问题 Shortest Path Problem Ch6 网络模型网络模型 Network Model Page 50 2021-10-14237184562421182151124829 现问从现问从u u1 1到到u u8 8, ,的各条链中的各条链中, ,哪一条的总长度最短哪一条的总长度最短? ?（0 0，1 1） 8211（2 2，1 1） Ch6 网络模型网络模型 Network Model Page 51 2021-10-14 现问从现问从u u1 1到到u u8 8, ,的各条链中的各条链中, ,哪一条的总长度最短哪一条的总长度最短? ?（0，1）

40、2371845624211821511248298211（2 2，1 1） 67（4 4，3 3） 4最短链问题最短链问题Ch6 网络模型网络模型 Network Model Page 52 2021-10-14 现问从现问从u u1 1到到u u8 8, ,的各条链中的各条链中, ,哪一条的总长度最短哪一条的总长度最短? ?（0，1）2371845624211821511248298211（2 2，1 1） 67（4 4，3 3） 4516（5 5，4 4） 最短链问题最短链问题Ch6 网络模型网络模型 Network Model Page 53 2021-10-14 现问从现问从u u1

41、1到到u u8 8, ,的各条链中的各条链中, ,哪一条的总长度最短哪一条的总长度最短? ?（0，1）2371845624211821511248298211（2 2，1 1） 67（4 4，3 3） 4516（5 5，4 4） 7139（6 6，3 3） 最短链问题最短链问题Ch6 网络模型网络模型 Network Model Page 54 2021-10-14 现问从现问从u u1 1到到u u8 8, ,的各条链中的各条链中, ,哪一条的总长度最短哪一条的总长度最短? ?（0，1）2371845624211821511248298211（2 2，1 1） 67（4 4，3 3） 451

42、6（5 5，4 4） 7139（6 6，3 3） 15（7 7，6 6） 最短链问题最短链问题Ch6 网络模型网络模型 Network Model Page 55 2021-10-14 现问从现问从u u1 1到到u u8 8, ,的各条链中的各条链中, ,哪一条的总长度最短哪一条的总长度最短? ?（0 0，1 1） 2371845624211821511248298211（2 2，1 1） 67（4 4，3 3） 4516（5 5，4 4） 7139（6 6，3 3） 15（7 7，6 6） 8（8 8，5 5） 最短链问题最短链问题Ch6 网络模型网络模型 Network Model Pa

43、ge 56 2021-10-14从从u u1 1到到u u8 8, ,的各条链中的各条链中, , 最短链为最短链为1-3-4-6-581-3-4-6-58（0 0，1 1） 2371845624211821511248298211（2 2，1 1） 67（4 4，3 3） 4516（5 5，4 4） 7139（6 6，3 3） 15（7 7，6 6） 8（8 8，5 5） 最短链问题最短链问题Ch6 网络模型网络模型 Network Model Page 57 2021-10-14对于对于wij0时可用时可用D氏算法，当氏算法，当wij0时，则可能失效。时，则可能失效。 231-424231-

44、424（0，0）42（2，1）最短路径为最短路径为1-2-3 ，最短距离为，最短距离为0因此当负权时因此当负权时, 需要用求负权最短路问题的需要用求负权最短路问题的Filoyd算法算法. 6.2.4 最短路的最短路的Floyd算法算法 Ch6 网络模型网络模型 Network Model Page 58 2021-10-14 Floyd 算法算法回路(u2, u3, u4, u2,)的长是-2,故从u1到u5的最短路的长度无下界,因此在研究最短路问题时,常设图中不存在负回路,在此假设下,从一点到另一点的最短路总可以取成初等路. 如果一个有向图如果一个有向图D中存在权为负数的回路中存在权为负数的

45、回路(称为负回路称为负回路) ，这样两点间最短路的长度就没有下界。这样两点间最短路的长度就没有下界。 421352132-51Ch6 网络模型网络模型 Network Model Page 59 2021-10-14Floyd算法基本步骤算法基本步骤 :(1)写出写出vi一步到达一步到达vj 的距离矩阵的距离矩阵 ，L1也是一步到达的也是一步到达的最短距离矩阵。如果最短距离矩阵。如果vi 与与vj 之间没有边关联，则令之间没有边关联，则令cij=+ (1)1()ijLL(2)计算二步最短距离矩阵。设计算二步最短距离矩阵。设vi 到到vj 经过一个中间点经过一个中间点vr 两步到达两步到达vj，

46、则，则vi到到vj的最短距离为的最短距离为(2)minijirrjrLcc最短距离矩阵记为最短距离矩阵记为 (2)2()ijLL(3)计算计算k步最短距离矩阵。设步最短距离矩阵。设 vi经过中间点经过中间点vr 到达到达vj，vi 经过经过k1步到达点步到达点vr 的最短距离为的最短距离为 ，vr 经过经过k1步到达点步到达点vj 的最短的最短距离为距离为 ，则，则 vi 经经k步步 到达到达vj 的最短距离为的最短距离为(1)krjL(1)krjL(6.1)6.2 最短路问题最短路问题 Shortest Path Problem Ch6 网络模型网络模型 Network Model Page

47、 60 2021-10-14( )(1)(1)minkkkijirrjrLLL最短距离矩阵记为最短距离矩阵记为 ( )()kkijLL(4)比较矩阵比较矩阵Lk与与Lk1，当，当LkLk1时得到任意两点间的最短距时得到任意两点间的最短距离矩阵离矩阵Lk。设图的点数为设图的点数为n并且并且cij0，迭代次数，迭代次数k由式由式(6.3) 估计得到。估计得到。 (6.2)121221kknlg(1)1lg 2nkk(6.3)6.2 最短路问题最短路问题 Shortest Path Problem Ch6 网络模型网络模型 Network Model Page 61 2021-10-14634521

48、2789326121610【例【例6.6】图】图6-14是一张是一张8个城市的铁路交通图，铁路部门要制作个城市的铁路交通图，铁路部门要制作一张两两城市间的距离表。这个问题实际就是求任意两点间的最一张两两城市间的距离表。这个问题实际就是求任意两点间的最短路问题。短路问题。【解】【解】 (1)依据图依据图6-14,写出写出任意两点间一步到达距离任意两点间一步到达距离表表L1。见表所示。本例。见表所示。本例n=8， ，因此计，因此计算到算到L3 图图6-14lg72.807lg26.2 最短路问题最短路问题 Shortest Path Problem Ch6 网络模型网络模型 Network Mod

49、el Page 62 2021-10-14v1v2v3v4v5v6v7v8v10 06 65 54 4v26 60 03 32 28 8v33 30 07 71616v45 52 20 09 912123 3v58 87 79 90 010106 6v64 412120 02 2v73 310102 20 01212v816166 612120 0表表6-1 最短距离表最短距离表 L16.2 最短路问题最短路问题 Shortest Path Problem Ch6 网络模型网络模型 Network Model Page 63 2021-10-14表表6-2 最短距离表最短距离表L2v1v2v3

50、v4v5v6v7v8v106951446v26032810514v3930571713v4525095315v514879012106v64105120214v765173102012v8141315614120计算说明：计算说明：L(2)ij等于表等于表6-1中第中第i行与第行与第j列对应元素相加取最小值。如列对应元素相加取最小值。如 4341134223433344434553466347734883min,min 5,23,0,0,97,0,10,6165Lcccccccccccccccc (2)6.2 最短路问题最短路问题 Shortest Path Problem Ch6 网络模型网

51、络模型 Network Model Page 64 2021-10-14表表6-3计算示例计算示例: 等于表等于表6-2中第中第i行与第行与第j列对应元素相加取最小值。例如，列对应元素相加取最小值。例如，v3经过三步（最多三个中间点经过三步（最多三个中间点4条边）到达条边）到达v6的最短距离是的最短距离是表表6-3 最短距离表最短距离表L3v1v2v3v4v5v6v7v8v10695144618v2603287514v39305710813v4525095315v514879012106v647105120214v76583102012v818141315614120(3)ijL2222363

52、116322633363886min,min 94,310,0,55,712,0,172,131410LLLLLLLLL (3)(2)(2)(2)(2)6.2 最短路问题最短路问题 Shortest Path Problem Ch6 网络模型网络模型 Network Model Page 65 2021-10-14【例【例6.7】求图】求图615中任意两点间的最短距离。中任意两点间的最短距离。【解】图【解】图615是一个混合图，有是一个混合图，有3条边的权是负数条边的权是负数,有两条边有两条边无方向。依据图无方向。依据图615,写出任意两点间一步到达距离表写出任意两点间一步到达距离表L1。表。

53、表中第一列的点表示弧的起点，第一行的点表示弧的终点，无方中第一列的点表示弧的起点，第一行的点表示弧的终点，无方向的边表明可以互达，见表向的边表明可以互达，见表6-4所示。计算过程见表所示。计算过程见表6-56-7。445743271028图图615156.2 最短路问题最短路问题 Shortest Path Problem Ch6 网络模型网络模型 Network Model Page 66 2021-10-14表表6-4一步到达距离表一步到达距离表L1v1v2v3v4v5v6v7v105 4v2042v34072v440107v5103v6508v7206.2 最短路问题最短路问题 Shor

54、test Path Problem Ch6 网络模型网络模型 Network Model Page 67 2021-10-14表表6-7 最短距离表最短距离表L4v1v2v3v4v5v6v7v10593419v2204-2635v364021072v44990857v5-14720-35v69141051308v786241290经计算经计算L4L5，L4是最优表。表是最优表。表6-7不是对称表，不是对称表，vi到到vj与与vj到到vi的的最短距离不一定相等。对于有负权图情形，公式最短距离不一定相等。对于有负权图情形，公式(6.3)失效。失效。 6.2 最短路问题最短路问题 Shortest

55、Path Problem Ch6 网络模型网络模型 Network Model Page 68 2021-10-14 Floyd 算法的内容算法的内容设给定有向图D=(V,E)及E上的权函数w(e)以wj表示从vi到vj的最短路的权, w=(vi,vj)仍简记为wij.又设V的点数为n,易知w1, w2, wn,必须满足如下方程: wj =min wi+wij, (vjV j=1,2,n)Ch6 网络模型网络模型 Network Model Page 69 2021-10-14 Floyd 算法的内容算法的内容 对一切i规定wii=0, 若V中的两点vi和vj之间无弧相连,则令w=(vi,vj

56、)=+,这样便可认为,任何两点之间都有弧相连了. 开始令wj(0)= w1j(j=1,2,n),一般地,设已有各个wj(k-1),则: wj(k)= min wi(k-1)+ wij (j=1,2,n) 当过程进行到某一步,发现每个j都有wj(k)= wj(k-1)时,则计算停止,此时wj(k)就是从vi到vj的最短路的权. 上述算法最多经过n-1次迭代必定收敛。若在已算出的wj(n-1)中至少有某个j,使得wj(n-1)wj(n-2), 说明图中有负回路，无最短路. 方程方程 wj =min wi+wij 的解可以用迭代法求得的解可以用迭代法求得,步骤如下步骤如下:Ch6 网络模型网络模型

57、Network Model Page 70 2021-10-14求求v v1 1到各点的最短路？到各点的最短路？ Floyd 算法示例算法示例433-4-27-132315-22254Ch6 网络模型网络模型 Network Model Page 71 2021-10-14 Floyd 算法示例算法示例 求解过程可在表上进行。表的左边是初始数据，右边是各次迭代的计算结果，最右边的一列数字就是从V1到各个VJ的最短路的权。Ch6 网络模型网络模型 Network Model Page 72 2021-10-14Floyd 算法示例算法示例wijv1v2v3v4v5v1 023v220-2v3-2

58、-40v4530-1v53740Wj(0) 0 2(1,2) 3(1,3) Wj(1) 0 -1(3,2) 3(1,3) 0(2,5)Wj(2) 0 -1(3,2) 3(1,3) 3(1,3) 3(1,3) 0 0 -1(3,2) -1(3,2) 4(5,4) 1(5,4) 1(5,4) -3(2,5) -3(2,5) -3(2,5)Wj(3)Wj(4)Ch6 网络模型网络模型 Network Model Page 73 2021-10-14 Floyd 算法示例算法示例 求求Wj(0) Wj(0) = W1j W11 = 0 W12 = 2 (1,2) W13 = 3 (1,3) W14 =

59、 W15 = Ch6 网络模型网络模型 Network Model Page 74 2021-10-14 Floyd 算法示例算法示例 求求Wj(1) Wj(1) = min Wi(0) + Wij W1(1) = min W1(0) + W11、 W2(0) + W21 W5(0) + W51 = min0+0、2+2、3-2=0 W2(1) = min W1(0) + W12、 W2(0) + W22 W5(0) + W52 = min0+2、2+0、3-4=-1（3，2） W3(1) = min W1(0) + W13、 W2(0) + W23 W5(0) + W53 = min0+3、

60、3+0=3（1，3） W4(1) = min W1(0) + W14、 W2(0) + W24 W5(0) + W53 = W5(1) = min W1(0) + W15、 W2(0) + W25 W5(0) + W55 = min2-2=0（2，5）Ch6 网络模型网络模型 Network Model Page 75 2021-10-14 Floyd 算法示例算法示例 求求Wj(2) Wj(2) = min Wi(1) + Wij W1(2) = min W1(1) + W11、 W2(1) + W21 W5(1) + W51 = min0+0、-1+2、3-2=0 W2(2) = min