物流运输路径规划

《物流运输路径规划》由会员分享，可在线阅读，更多相关《物流运输路径规划（48页珍藏版）》请在金锄头文库上搜索。

1、第六章第六章 物流运输路径规划物流运输路径规划主讲人：邓建新主讲人：邓建新主讲人：邓建新主讲人：邓建新2021/9/241n小李自广西大学营销专业毕业进入利客隆工作前天刚小李自广西大学营销专业毕业进入利客隆工作前天刚过过1年，昨天得到了一个好消息，公司调它到总部做配年，昨天得到了一个好消息，公司调它到总部做配送调度。小李送调度。小李very,very高兴，说公司很给力，决定一高兴，说公司很给力，决定一定要做好这份工作。而公司也希望借用小李的学识，定要做好这份工作。而公司也希望借用小李的学识，以以进一步规范企业配送，提高质量，降低成本，在沃进一步规范企业配送，提高质量，降低成本，在沃尔玛、南城百

2、货等大型超市挤压下争取生存机会。但尔玛、南城百货等大型超市挤压下争取生存机会。但对小李来说，调度还真是新鲜事。对于干了对小李来说，调度还真是新鲜事。对于干了1年的小李，年的小李，对公司的规模、布局了如指掌。对公司的规模、布局了如指掌。小李的难题小李的难题2021/9/242利客隆利客隆 超市分部图超市分部图总部总部怎么走，成本最低？应该先送哪一个商店？怎么走，成本最低？应该先送哪一个商店？现需要送现需要送20吨百货到吨百货到A、B等等10个分店，个分店，每个分店的需求都很零散，每个分店的需求都很零散，至少需要多少什么型号的车辆？至少需要多少什么型号的车辆？每天各个分店都有部分百货要运回或转移到

3、每天各个分店都有部分百货要运回或转移到其他分店，怎么运输车辆返空率最低，成本最低？其他分店，怎么运输车辆返空率最低，成本最低？2021/9/243小李的答案类似解小李的答案类似解2021/9/244太原重庆武汉南京徐州连云港上海郑州石家庄塘沽青岛济南天津北京长途运输路线问题长途运输路线问题2021/9/245n长虹街道近年新建了长虹街道近年新建了11个居民小区，各小区的大致位个居民小区，各小区的大致位置及相互间的道路距离如图所示，单位（置及相互间的道路距离如图所示，单位（100m），），各居住小区居民数为：各居住小区居民数为：2000, 3000, 3500, 3700, 5000, 2800

4、, 4500。1234567644722355672021/9/246政府的难题政府的难题n政府想在政府想在7个小区准备共建一套医务所、邮局、个小区准备共建一套医务所、邮局、储蓄所等服务设施，应建于哪一居民小区，使储蓄所等服务设施，应建于哪一居民小区，使对居民总体来说感到方便。对居民总体来说感到方便。n电信部分拟将布设宽带到各个小区，应如何铺电信部分拟将布设宽带到各个小区，应如何铺设最为经济？设最为经济？n工作组组织考察，从小区工作组组织考察，从小区出发，经过各小区出发，经过各小区（顺序不限），最后到小区（顺序不限），最后到小区再离去，哪条路再离去，哪条路最近？最近？2021/9/247第六章

5、第六章 物流运输路径规划物流运输路径规划第一节第一节第一节第一节 图的基本概念图的基本概念图的基本概念图的基本概念第二节第二节第二节第二节 最短路径问题最短路径问题最短路径问题最短路径问题 第三节第三节第三节第三节 最大流问题最大流问题最大流问题最大流问题 第四节第四节第四节第四节 最小费用流问题最小费用流问题最小费用流问题最小费用流问题 第五节第五节第五节第五节 单、多回路运输路线问题单、多回路运输路线问题单、多回路运输路线问题单、多回路运输路线问题 2021/9/248 图图论论是是应应用用非非常常广广泛泛的的运运筹筹学学分分支支，它它已已经经广广泛泛地地应应用用于于物物理理学学控控制制论

6、论，信信息息论论，工工程程技技术术，交交通通运运输输，经经济济管管理理，电电子子计计算算机机等等各各项项领领域域。对对于于科科学学研研究究，市市场场和和社社会会生生活活中中的的许许多多问问题题，可可以以同同图图论论的的理理论论和和方方法法来来加加以以解解决决。例例如如，各各种种通通信信线线路路的的架架设设，输输油油管管道道的的铺铺设设，铁铁路路或或者者公公路路交交通通网网络络的的合合理理布布局局等等问问题题，都都可可以以应应用用图图论论的的方方法法，简简便便、快快捷捷地地加加以解决。以解决。第六章第六章 物流运输路径规划物流运输路径规划2021/9/249 随随着着科科学学技技术术的的进进步步

7、，特特别别是是电电子子计计算算机机技技术术的的发发展展，图图论论的的理理论论获获得得了了更更进进一一步步的的发发展展，应应用用更更加加广广泛泛。如如果果将将复复杂杂的的工工程程系系统统和和管管理理问问题题用用图图的的理理论论加加以以描描述述，可可以以解解决决许许多多工工程程项项目目和和管管理理决决策策的的最最优优问问题题。因因此此，图图论论越越来来越越受受到到工程技术人员和经营管理人员的重视。工程技术人员和经营管理人员的重视。第六章第六章 物流运输路径规划物流运输路径规划2021/9/2410 17361736年年瑞瑞士士科科学学家家欧欧拉拉发发表表了了关关于于图图论论方方面面的的第第一一篇篇

8、科科学学论论文文与与位位置置几几何何有有关关的的一一个个问问题题的的解解 ，解解决决了了著著名名的的哥哥尼尼斯斯堡堡七七座座桥桥问问题题。17世世纪纪的的东东普普鲁鲁士士有有一一座座哥哥尼尼斯斯堡堡城城（现现在在叫叫加加里里宁宁格格勒勒，在在波波罗罗的的海海南南岸岸），城城中中有有一一条条普普雷雷格格尔尔河河，河河中中有有两两个个岛岛屿屿，河河的的两两岸岸和岛屿之间有七座桥相互连接，如下图所示。和岛屿之间有七座桥相互连接，如下图所示。第六章第六章 物流运输路径规划物流运输路径规划2021/9/2411第六章第六章 物流运输路径规划物流运输路径规划哥尼斯堡一角哥尼斯堡一角2021/9/2412B

9、ACD 当地的居民热衷于当地的居民热衷于这样一个问题，这样一个问题，一个漫一个漫步者如何能够走过这七步者如何能够走过这七座桥，并且每座桥只能座桥，并且每座桥只能走过一次，最终回到原走过一次，最终回到原出发地。出发地。尽管试验者很多，尽管试验者很多，但是都没有成功。但是都没有成功。第六章第六章 物流运输路径规划物流运输路径规划2021/9/2413 为为了了寻寻找找答答案案，17361736年年欧欧拉拉把把陆陆地地缩缩为为一一点点，把把桥桥作作为为连连接接点点的的边边，将将这这个个问问题题抽抽象象成成图图形形的的一一笔笔画画问问题题。即即能能否否从从某某一一点点开开始始不不重重复复地地一一笔笔画

10、画出出这这个个图图形形，最最终终回回到到原原点点。欧欧拉拉在在他他的的论论文文中中证证明明了了这这是是不不可可能能的的，因因为为这这个个图图形形中中每每一一个个顶顶点点都都与与奇奇数数条条边边相相连连接接，不不可可能能将将它它一一笔笔画画出出，这这就就是是古古典典图图论论中的第一个著名问题。中的第一个著名问题。BACD第六章第六章 物流运输路径规划物流运输路径规划2021/9/2414 在在实实际际的的生生产产和和生生活活中中，人人们们为为了了反反映映事事物物之之间间的的关系，常常在纸上用点和线来画出各式各样的示意图。关系，常常在纸上用点和线来画出各式各样的示意图。 例例 有有六六支支球球队队

11、进进行行足足球球比比赛赛，我我们们分分别别用用点点v1 1v6 6 表表示示这这六六支支球球队队，它它们们之之间间的的比比赛赛情情况况，也也可可以以用用图图反反映映出出来来，已已知知v1 1 队队战战胜胜v2 2 队队，v2 2 队队战战胜胜v3 3队队，v3 3 队队战战胜胜v5 5 队队，如如此此等等等等。这这个个胜胜负负情情况况，可可以以用用下下图所示的有向图反映出来。图所示的有向图反映出来。第一节第一节第一节第一节 图的基本概念图的基本概念图的基本概念图的基本概念第六章第六章 物流运输路径规划物流运输路径规划2021/9/2415v v3 3v v1 1v v2 2v v4 4v v6

12、 6v v5 5第一节第一节 图的基本概念图的基本概念2021/9/2416 我我们们就就把把类类似似以以上上的的几几个个例例子子中中通通过过点点和和点点之之间间的的线线来来反反映映实实际际生生产产和和生生活活中中的的某某些些特特定定对对象象之之间间的的特特定定关关系系的的所所构构成成图图形形称称为为图图（GraphGraph）。一一般般来来说说，通通常常用用点点表表示示研研究究对对象象, ,用用点点与与点点之之间间的的线线表表示示研研究究对对象象之之间间的的特特定定关关系系。由由于于在在一一般般情情况况下下，图图中中的的相相对对位位置置如如何何，点点与与点点之之间间线线的的长长短短曲曲直直，

13、对对于于反反映映研研究究对对象象之之间间的的关关系系，显显的的并并不不重重要要，因因此此，图图论论中中的的图图与几何图，工程图等本质上是不同的。与几何图，工程图等本质上是不同的。第一节第一节 图的基本概念图的基本概念2021/9/2417 图图论论中中所所研研究究的的图图，是是指指反反映映或或描描述述自自然然界界或或人人类类社社会会中中，大大量量的的事事物物及及事事物物之之间间关关系系的的图图形形。是是由由由由点点点点和和和和线线线线组组组组成成成成的的的的。点点点点称称称称为为为为顶顶顶顶点点点点，它它的的集集合合用用V（Vertex）表表示示，顶顶点点通通常常表表示示有有形形或或无无形形的

14、的事事物物。线线线线称称称称为为为为边边边边，它它的的集集合合用用E（Edge）表表示示，边边通通常常表表示示事事物物与与事事物物（点点与与点点）之之间间的的联联系系或或特特定定的的关系。关系。一、图的定义一、图的定义一、图的定义一、图的定义第一节第一节 图的基本概念图的基本概念2021/9/2418 例例例例1 1 某某地地区区有有五五个个镇镇A、B、C、D、E它它们们之之间间有有公公路路相相通通的的情情况况如如图图所所示。示。一、图的定义一、图的定义2021/9/2419 在图论中，我们只关心在图论中，我们只关心两点间是否有联系两点间是否有联系，至于至于公路的大小、等级、状况均无关紧要，亦

15、即公路的大小、等级、状况均无关紧要，亦即不考虑线不考虑线段（边）的长度段（边）的长度，点的位置带有随意性点的位置带有随意性，它们，它们并不按并不按比例尺画比例尺画，如五个镇之间的连接图也可画成右图表示。，如五个镇之间的连接图也可画成右图表示。 ABCDE一、图的定义一、图的定义2021/9/2420 定定定定义义义义1 1： 一一个个图图是是由由点点集集V=vi 和和V中中元元素素的的无无序序对对集集E= ek 所所构构成成的的二二元元组组，记记作作：G =（V，E），其其中中 vi 称称为为顶顶点点，ek 称称为为边边。|V | 表表示示顶顶点点个个数数，|E | 表表示示边边的的个个数数。

16、当当V和和E都都是是有有限限集集合合时时，G为为有有限限图图，否否则则，称称为为无无限限图图。本本书书只只论论及及有有限限图图。图图中中所所有有边边都都没没有有方方向向，称称为为无无向向图图，否否则则称称为为有有向向图图。例例如如下下面面图图6-3-3，即即为无向图为无向图.一、图的定义一、图的定义2021/9/2421无向图无向图G =（V，E） 其中：其中：V v1、v2、v3、v4、v5 E e1、e2、e3、e4、e5、e6、e7并且：并且： e 1 （v1、v2） e 2（v1、v2） e 3 （v1、v3） e 4 （v1、v4） e 5 （v3、v4） e 6 （v3、v3） e

17、 7 （v2、v5）一、图的定义一、图的定义图6-32021/9/2422v v3 3v v1 1v v2 2v v4 4v v6 6v v5 5第一节第一节 图的基本概念图的基本概念有向图有向图D（V，A）V为顶点集为顶点集A（arc）为边或弧）为边或弧2021/9/2423关关关关联联联联边边边边：和和同同一一个个顶顶点点相相连连的的边边，均均称称为为该该点点的的关关联联边边，如如图图6-4-4中中的的e24、e34、e45均均是是v4的的关关联边。联边。相相相相邻邻邻邻点点点点：一一条条边边的的两两个个顶顶点点，称称为为相相邻邻点点，如如v2与与v4，v4与与v5等等是是相相邻邻点，而点

18、，而v2与与v5则不是。则不是。一、图的定义一、图的定义图图 6-4 6-42021/9/2424一、图的定义一、图的定义 环环环环与与与与多多多多重重重重边边边边：两两个个顶顶点点相相同同的的边边称称为为环环，如如e2222，两两个个顶顶点点之之间间的的边边数数22时时, ,叫叫多多 重重 边边 , ,如如 e13 13 , ,e1313就是二重边。就是二重边。图图 6-4 6-4二重边二重边二重边二重边环环环环2021/9/2425次次次次：一一个个顶顶点点v具具有有关关联联边边的的总总数数称称为为该该顶顶点点的的次次，记作记作d(v)（每个环视作两条边），如图（每个环视作两条边），如图6

19、-46-4。 d(v1)= 3= 3，d(v2)= 4= 4， d(v5)= 1= 1。 把次为奇数的顶点称把次为奇数的顶点称 为为奇顶点奇顶点，次为偶数，次为偶数 的顶点称为的顶点称为偶顶点偶顶点。图图 6-4 6-4一、图的定义一、图的定义2021/9/2426一、图的定义一、图的定义悬挂点与孤立点悬挂点与孤立点悬挂点与孤立点悬挂点与孤立点： 次次为为1 1的的顶顶点点称称为为悬悬挂挂点点，如如v5 5。次次为为0 0的的顶顶点点称称为为孤孤立立点点，如如v6 6。图图 5-4 5-4v6 6孤孤孤孤立立立立点点点点悬悬悬悬挂挂挂挂点点点点2021/9/2427简简简简单单单单图图图图：无

20、无环环、无无多多重重边边的的图图称称为为简简单单图图，如如图图6-4(a)6-4(a)、(b)(b)、(c)(c)，后面如无特殊说明，均指简单图。，后面如无特殊说明，均指简单图。一、图的定义一、图的定义图6-4（a）图6-4（b）图6-4（c）2021/9/2428子子子子图图图图与与与与支支支支撑撑撑撑子子子子图图图图：在在图图G=(V，E)中中，若若V1 V，E1 E，则则图图G1=(V1、E1)称称为为G的的子子图图，如如图图6-46-4中中的的(b)就就是是(a)的的子子图图。特特别别地地：V1=V，E1 E时时，称称G1是是G的的支支撑撑子子图图( (生成子图）。如图生成子图）。如图

21、6-46-4中中(c)、(b)都是都是(a)的支撑图。的支撑图。一、图的定义一、图的定义图6-4（a）图6-4（b）图6-4（c）2021/9/2429定理定理定理定理1 1 1 1 在任何图中顶点次数总和等于边数的在任何图中顶点次数总和等于边数的2 2倍。倍。定理定理定理定理2 2 2 2 任何图中，次为奇数的顶点必有偶数个。任何图中，次为奇数的顶点必有偶数个。 即奇顶点必有偶数个。即奇顶点必有偶数个。一、图的定义一、图的定义2021/9/2430二、连通图二、连通图定定定定义义义义2 2 2 2 无无向向图图G=(V，E)中中，称称某某些些点点及及其其关关联联边边的的交交替替序序列列v1

22、e1 v2 e2 en vn 为为从从v1到到vn的的一一条条链链，v1、vn分别称为链的分别称为链的始点始点和和终点终点，链长为，链长为n。 若若一一条条链链的的始始点点与与终终点点重重合合，则则称称为为闭闭链链( (在在无无向向图图中中闭闭链链又又称称为为回回路路），否否则则，称称为为开开链链。点点边边序序列列中中若若只只有有重重复复的的点点而而无无重重复复的的边边，则则称称为为简简单单链链。点点边边序序列列中中若若既既没没有有重重复复的的点点也也无无重重复的边，则称为复的边，则称为初等链初等链（也称为（也称为通路通路）。）。2021/9/2431例如在图例如在图6-5中：中： S=v6

23、e6 v5 e7 v1 e8 v5 e7 v1 e9 v4 e4 v3是一是一条连接条连接v6、v3的链，链长为的链，链长为6. S1=v6 e6 v5 e7 v1 e8 v5 e5 v4 e4 v3是一条连接是一条连接v6、v3的简单的简单链，链长为链，链长为5.S2=v6 e6 v5 e7 v1 e9 v4 e4 v3是一条连接是一条连接v6、v3的初等链。的初等链。 e1e2 e3 e4e6 e7 e8 e9 e10 v1v2 v3 v4v5v6e5二、连通图二、连通图图图图图6-56-56-56-52021/9/2432连通的连通的连通的连通的 在无向图中，若顶点在无向图中，若顶点vi

24、与与vj之间存在链，之间存在链， 则称则称vi与与vj是是连通的连通的。规定：规定：规定：规定： vi与自身是连通的与自身是连通的连通图连通图连通图连通图 若无向图若无向图G中的任意两个顶点都是连通的，中的任意两个顶点都是连通的， 则称则称G是是连通图连通图，否则称否则称G是是非连通图非连通图。二、连通图二、连通图2021/9/24333. 3. 网网 络络 一个图连同定义在其边集上的实函数一起称为一一个图连同定义在其边集上的实函数一起称为一个网络网络一般是连通图定义在边集上的实函数个网络网络一般是连通图定义在边集上的实函数称为边的权数记为称为边的权数记为 wijw (vi，vj) 它它与与边

25、边(vi，vj)具具有有一一一一对对应应关关系系，可可以以用用以以表表达达网网络络上上的的各各种种有有关关性性质质，如如路路长长、流流量量、费费用用等等等等网络的图解即在每条边旁标上相应的权数网络的图解即在每条边旁标上相应的权数 若若一一网网络络的的每每条条边边都都是是无无向向边边，则则称称为为无无向向网网络络，记为记为N( (G，w ) ) 或或 N(V，E ) 2021/9/2434 若一网络的每条边都是有向边，则称为有向网络，若一网络的每条边都是有向边，则称为有向网络，记为记为 N( D，w ) 或或 N ( V，A ) 若一网络中既有无向边，也有有向边，则称为混合若一网络中既有无向边，

26、也有有向边，则称为混合网络网络 所谓网络分析，即对网络进行定性和定量分析，以便所谓网络分析，即对网络进行定性和定量分析，以便为实现某种优化目标而寻求最优方案这方面的典型问题为实现某种优化目标而寻求最优方案这方面的典型问题有：最小树问题有：最小树问题，最短路问题，最短路问题，中心问题，重心问题，中心问题，重心问题，最最大流问题大流问题，最小费用最大流问题最小费用最大流问题，网络计划问题网络计划问题，等等，等等 3. 3. 网网 络络 2021/9/2435 从从v v1 1到到v v6 6的的路路线线是是很很多多的的。比比如如从从v v1 1出出发发，经经过过v v2 2 ,v,v4 4到到达达

27、v v6 6或或者者从从v v1 1出出发，经过发，经过v v2 2，v v3 3，v v5 5到达到达第二节第二节第二节第二节 最短路径问题最短路径问题最短路径问题最短路径问题 v6v5v3v1v4v2365112436 v v6 6等等等等。但但不不同同的的路路线线，经经过过的的总总长长度度是是不不同同的的。例例如如，按按照照第第一一个个线线路路，总总长长度度是是3+6+3=123+6+3=12单单位位，按按照照第第二二个个路路线线，总长度是总长度是3+1+1+6=113+1+1+6=11单位。单位。2021/9/2436第二节第二节第二节第二节 最短路径问题最短路径问题最短路径问题最短路

28、径问题 基本算法有两种基本算法有两种：Dijkstra算法：求某一点到其他各点之间的最短距离算法：求某一点到其他各点之间的最短距离矩阵算法：求任意两点之间的距离。矩阵算法：求任意两点之间的距离。2021/9/2437第二节第二节第二节第二节 最短路径问题最短路径问题最短路径问题最短路径问题 1 1、双双双双标标标标号号号号法法法法（Dijkstra算算法法），它它是是在在19591959年年提提出出来来的的。目目前前公公认认，在在所所有有的的权权wij 00时时，这这个个算算法法是是寻寻求求最最短短路路问问题题最最好好的的算算法法。并并且且，这这个个算算法法实实际际上上也也给出了寻求从一个始定

29、点给出了寻求从一个始定点vs到任意一个点到任意一个点vj的最短路。的最短路。二、最短路问题的算法二、最短路问题的算法二、最短路问题的算法二、最短路问题的算法 2021/9/2438第二节第二节第二节第二节 最短路径问题最短路径问题最短路径问题最短路径问题 DijkstraDijkstra算法算法算法算法 1234假定1234是14的最短路。则123一定是13的最短路，234也一定是24的最短路。2021/9/2439第二节第二节第二节第二节 最短路径问题最短路径问题最短路径问题最短路径问题 DijkstraDijkstra算法算法算法算法 1234反证：设13的最短路为153。则1534的路长

30、肯定小于1234。这与假设矛盾。52021/9/2440第二节第二节第二节第二节 最短路径问题最短路径问题最短路径问题最短路径问题 DijkstraDijkstra算法算法算法算法 设dij表示两个相邻点ij点距离；如果不相邻 设Lsi表示不相邻的S-i之间的距离。 为了标志最短路的点，就对其标号。整个方法里面有两种标号： （1）最短路上的点的标号，用P（permanent）表示; （2）不是最短路上的点的标号，用T(temporary)表示。2021/9/2441第二节第二节第二节第二节 最短路径问题最短路径问题最短路径问题最短路径问题 DijkstraDijkstra算法算法算法算法 步骤

31、： （1）初始化，从起点s出发，给起点标P号，距离值为0，即P(s) =0, 其余个点标T号，距离为 。 （2）考察与s相应的点，计算s到这些点的距离 然后，在所有标T号的点中，选择距离最小的那个标P号。2021/9/2442第二节第二节第二节第二节 最短路径问题最短路径问题最短路径问题最短路径问题 DijkstraDijkstra算法算法算法算法 步骤： （3）考察新P的点，方法同（2），直到所有点都都考察完毕，标上P号。 （4）根据P号点距离值的来源，追溯最短路径即求出最短路。2021/9/2443二、最短路问题的算法二、最短路问题的算法二、最短路问题的算法二、最短路问题的算法 例例6 求

32、求v1到到v6的最短路。的最短路。+（1 1）首先给）首先给v1以以P标号标号，P P( (v1) )0 0，给其余所有点，给其余所有点T标号，标号，T( (vj) )（ j = 2= 2，3 3， 6) 6)(0)(0) P标号以标号以（ ）形式标形式标在结点旁边，在结点旁边，T标号以不标号以不带（）的数字标在结点带（）的数字标在结点旁边旁边 .v6v5v3v1v4v23651124362021/9/2444二、最短路问题的算法二、最短路问题的算法二、最短路问题的算法二、最短路问题的算法 P(P(v2 )= )= 3 3 3 3 （3 3）5 5 5 5P(P(v3 )= )= 4 4 4

33、4 （4 4）+v6v5v3v1v4v2365112436+(0)(0)9 9（2 2）考察）考察 v1: : T( (v2)=)=min min T( (v2) )，P(P(v1) ) +a12 min min ，0 03 = 33 = 3T( (v3)=)=min min T( (v3) )，P(P(v1) ) +a13 min min ，0 05 = 55 = 5所以，所以，P(P(v2 )= )= 3 3 3 3（3 3）考察）考察 v2: :T( (v3)=)=min min T( (v3) )，P(P(v2) ) +a23 min 5min 5，3 31 = 41 = 4T( (v

34、4)=)=min min T( (v4) )，P(P(v2) ) +a24 min min ，3 36 = 96 = 9所以，所以，P(P(v3)=)=4 4 4 4T(T(v3 )= )= 5 5 5 5 T(T(v4)= )= 9 9 9 9 2021/9/2445二、最短路问题的算法二、最短路问题的算法二、最短路问题的算法二、最短路问题的算法 P(P(v5)= )= 5 5 5 5（3 3）（4 4）v6v5v3v1v4v2365112436+(0)(0)9 9（5 5）T(T(v4)= )= 8 8 8 8 （4 4）考察）考察 v3: : T( (v5)=)=min min T( (

35、v5) )，P(P(v3) ) +a35 min min ，4 41 = 51 = 5T( (v4)=)=min min T( (v4) )，P(P(v3) ) +a34 min 9min 9，4 44 = 84 = 8所以，所以，P(P(v5)= )= 5 5 5 5（5 5）考察）考察 v5: :T( (v6)=)=min min T( (v6) )，P(P(v5) ) +a56 min min ，5 56 = 116 = 11T( (v4)=)=min min T( (v4) )，P(P(v5) ) +a54 min 8min 8，5 52 = 72 = 7所以，所以，P(P(v4)=

36、)= 7 7 7 7 8 8T(T(v6)= )= 11111111 1111（7 7）P(P(v4)= )= 7 7 7 7 2021/9/2446二、最短路问题的算法二、最短路问题的算法二、最短路问题的算法二、最短路问题的算法 （3 3）（4 4）v6v5v3v1v4v23651124361111(0)(0)（5 5）（7 7）（6 6）考察）考察 v4: :T( (v6)=)=min min T( (v6) )，P(P(v4) ) +a46 min 11min 11，7 73 = 103 = 10所以，所以，P(P(v6)= )= 10101010所有点都所有点都标上上 P P 标号号

37、P(P(v6)= )= 10 10 10 10 (10)(10)(10)(10)(7) (7) 标出最短路标出最短路 v1到到v6的最短路的最短路可从可从v1开始，根据永久性标号开始，根据永久性标号数值回溯得到数值回溯得到2021/9/2447(7) (7) 标出最短路标出最短路 最短路径是：最短路径是：v1v2v3v5v4v6 ，路长，路长1010同同 时得到，到其余各点的最短路，即各点的永久性标号时得到，到其余各点的最短路，即各点的永久性标号P P（vi） 注意：注意： 双标号法只适双标号法只适用于所有用于所有wij 00的情形，当赋权的情形，当赋权有向图中存在负有向图中存在负权时，则算法失权时，则算法失效效 （3 3）（4 4）v6v5v3v1v4v2365112436(0)(0)（5 5）（7 7）(10)(10)(10)(10)二、最短路问题的算法二、最短路问题的算法二、最短路问题的算法二、最短路问题的算法 2021/9/2448