运筹学：第十章--图与网络分析课件.ppt

《运筹学：第十章--图与网络分析课件.ppt》由会员分享，可在线阅读，更多相关《运筹学：第十章--图与网络分析课件.ppt（118页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、图论图论应用十分广泛（物理学、信息科学、管理科学、应用十分广泛（物理学、信息科学、管理科学、社会科学、电子计算机）社会科学、电子计算机）第十章第十章 图与网络分析图与网络分析生产过程生产过程邮递员问题邮递员问题通信网络、交通网络通信网络、交通网络20世纪世纪50年代年代发展迅速发展迅速数学、工程技术、经营管理数学、工程技术、经营管理费用最省费用最省距离最短距离最短1图论图论的的起源与发展起源与发展 1736年，年，Euler哥尼斯堡七桥问题哥尼斯堡七桥问题(Knigsberg Bridge Problem)BACD一笔画定理：一笔画定理：连通图中，与偶连通图中，与偶数条线相连的点叫偶点，与奇数

2、条线相连的点叫偶点，与奇数条线相连的点叫奇点，奇点数条线相连的点叫奇点，奇点个数超过两个的图形不能一笔个数超过两个的图形不能一笔画出。画出。ABCD第十章第十章 图与网络分析图与网络分析哥尼斯堡哥尼斯堡东普鲁士东普鲁士Pregel 河河2 1847年，年，kirchhoff，电网络；电网络；1852年，年，四色猜想四色猜想（Four Color Theorem）；）；“任何一张任何一张地图地图只用四种颜色就能使具有共同边界的只用四种颜色就能使具有共同边界的国家着上不同的颜色。国家着上不同的颜色。”古德里古德里德德.摩尔根摩尔根汉密尔顿汉密尔顿19761976年年电气工程领域电气工程领域3 18

3、57年，年，Cogley，同分异构，同分异构，“树树”；合合肥肥工工业业大大学学组织部组织部党校党校宣传部宣传部人事处人事处教务处教务处财务处财务处学位与学科建设处学位与学科建设处.人事科人事科师资科师资科人才交流中心人才交流中心劳动与社会保障科劳动与社会保障科学术办公室学术办公室学位办公室学位办公室学科建设办公室学科建设办公室211211工程建设办公室工程建设办公室4 1956年，杜邦公司，年，杜邦公司，CPM，关键路线法；关键路线法；Critical Path Method 19561956年，美国杜邦公司在制定企业不同业务部门的系年，美国杜邦公司在制定企业不同业务部门的系统规划时，制订了

4、一套网络计划。这种计划借助于网统规划时，制订了一套网络计划。这种计划借助于网络表示各项工作与所需要的时间，以及各项不同工作络表示各项工作与所需要的时间，以及各项不同工作之间的关系。之间的关系。工程费用工程费用工期工期关键路线关键路线缩短工期、提高工效、降低成本缩短工期、提高工效、降低成本5 1958年，美国海军部，年，美国海军部，PERT，计划评审技术；计划评审技术；Project Evaluation and Review Technique 美国美国海军海军于于2020世纪世纪5050年代后期实施了研制年代后期实施了研制导弹导弹核核潜艇潜艇的计划（的计划（“北极星北极星”导弹计划导弹计划-

5、PolarisMissileProject）。由于实施计划的过程中用网络技术创造了）。由于实施计划的过程中用网络技术创造了一种控制工程进度的新方法一种控制工程进度的新方法计划评审技术，使北计划评审技术，使北极星导弹提前两年研制成功。这种方法在工程管理中极星导弹提前两年研制成功。这种方法在工程管理中产生的效益引起了人们的关注，促进了系统工程被广产生的效益引起了人们的关注，促进了系统工程被广泛应用于管理。泛应用于管理。6 1962年，管梅谷，年，管梅谷，中国邮路问题中国邮路问题；小学一年级数学题雷到众网友小学一年级数学题雷到众网友 邮递员叔叔要把信送往各地点，邮递员叔叔要把信送往各地点，“”代表送

6、信地点。代表送信地点。由于送信地点多，道路不好走（两个送信地点之间必须要由于送信地点多，道路不好走（两个送信地点之间必须要经过一个空白方格经过一个空白方格“”，而且不能走对角），还要绕过楼，而且不能走对角），还要绕过楼房，出发前他设计了一条送信路线，从邮局出发不但把信房，出发前他设计了一条送信路线，从邮局出发不但把信送到了每一个地点，而且路线不重复，最后回到邮局。送到了每一个地点，而且路线不重复，最后回到邮局。7 1965年，华罗庚，年，华罗庚，统筹方法平话统筹方法平话。“统筹方法统筹方法”是一种为生产建设服务的数学方法。是一种为生产建设服务的数学方法。它的实用范围极为广泛，在国防、在工业的生

7、产管它的实用范围极为广泛，在国防、在工业的生产管理中和关系复杂的科研项目的组织和管理中，都可理中和关系复杂的科研项目的组织和管理中，都可应用。应用。统筹方法平话统筹方法平话是著名数学家华罗庚教授是著名数学家华罗庚教授1965 1965 年年6 6 月月6 6 日在日在“人民日报人民日报”公布发表的第一篇网公布发表的第一篇网络计划技术文章。络计划技术文章。8第十章第十章 图与网络分析图与网络分析第一节第一节 图的基本概念图的基本概念第二节第二节 树树第三节第三节 最短路问题最短路问题第四节第四节 网络最大流问题网络最大流问题第五节第五节 最小费用最大流问题最小费用最大流问题第六节第六节 中国邮递

8、员问题中国邮递员问题9一、引例一、引例例例1 1 北京、上海等十北京、上海等十个城市间的铁路交通个城市间的铁路交通图。图。北京北京天津天津济南济南青岛青岛武汉武汉南京南京上海上海郑州郑州连云港连云港徐州徐州第一节第一节 图的基本概念图的基本概念与此类似的还有电话与此类似的还有电话线分布图、煤气管道线分布图、煤气管道图、航空路线图、公图、航空路线图、公路交通图等。路交通图等。10例例2 2 分别用点分别用点v1,v2,v3,v4,v5分别代表甲、乙、丙、丁、戊分别代表甲、乙、丙、丁、戊五支球队。若有两支球队之间比赛过，就在相应的点之间五支球队。若有两支球队之间比赛过，就在相应的点之间联一条线，且

9、这条线不过其他点。如下图所示：联一条线，且这条线不过其他点。如下图所示：v1v2v3v4v5由图可知各队之间的比赛情况由图可知各队之间的比赛情况如下：如下：甲甲 乙、丙、丁、戊乙、丙、丁、戊乙乙 甲、丙甲、丙丙丙 甲、乙、丁甲、乙、丁丁丁 甲、丙、戊甲、丙、戊戊戊 甲、丁甲、丁11例例3(3(加工方案问题加工方案问题)已知有已知有x1,x2,x3,x4,x5x1,x2,x3,x4,x5五台机床被五台机床被安排加工安排加工y1,y2,y3,y4,y5y1,y2,y3,y4,y5，我们知道机床，我们知道机床x1x1可加工零可加工零件件y1,y3,y5y1,y3,y5，机床，机床x2x2可加工零件可

10、加工零件y1,y4y1,y4，机床，机床x3x3可加工可加工零件零件y2,y4y2,y4，机床，机床x4x4可加工零件可加工零件y3,y4y3,y4，机床，机床x5x5可加工可加工零件零件y1y1。问能否制定一种加工方案，使一台机床只加。问能否制定一种加工方案，使一台机床只加工一种零件。工一种零件。x1 x2 x3 x4 x5x1 x2 x3 x4 x5y1 y2 y3 y4 y5y1 y2 y3 y4 y512点点：研究对象研究对象点与点之间的连线点与点之间的连线：研究对象之间的关系研究对象之间的关系点的相对位置 长短曲直 不重要甲甲 乙、丙、丁、戊乙、丙、丁、戊乙乙 甲、丙甲、丙丙丙 甲、

11、乙、丁甲、乙、丁丁丁 甲、丙、戊甲、丙、戊戊戊 甲、丁甲、丁v2v3v4v5v113 边边 两点之间不带箭头的联线。两点之间不带箭头的联线。如如e3.记为记为e3=v1,v4或或v4,v1v1v4a3 弧弧 两点之间带箭头的联线。两点之间带箭头的联线。如如a3.记为记为a3=（v1,v4）v1v4e3 端点及关联边端点及关联边若边若边e=u,v，则称则称u,v 为为e 的的端点端点，也称，也称u,v是是相邻相邻的，称的，称e是点是点u(及点及点v)的的关联边关联边。如：如：v1,v4为为e3的端点，的端点，v1,v4是是相邻的，相邻的，e3 是是v1（v4）的）的关联边。关联边。二、基本概念二

12、、基本概念vi,vj（vi,vj）弧弧a=(u,v),称称u是是a的的始点始点，v是是a的的终点终点，称弧，称弧a是从是从u指向指向v的的 始点和终点始点和终点v2v3v4v5v1图图是由一些点以及这些点之间的连线所组成的。是由一些点以及这些点之间的连线所组成的。14 有向图有向图 由点及弧所构成的图，记为由点及弧所构成的图，记为D=(V,A)，V,A分别是分别是D的的点集合与弧集合。点集合与弧集合。无向图无向图 由点及边所构成的图。记为由点及边所构成的图。记为G=(V,E),V,E分别是分别是G的点的点集合与边集合。集合与边集合。v1v2v3v4v1v2v3v4a1a2a3a4a5e1e2e

13、3e4e5a6e6V=v1,v2,v3,v4E=e1,e2,e3,e4,e5,e6V=v1,v2,v3,v4A=a1,a2,a3,a4,a5,a615 环环若在图若在图G中，某个边中，某个边e的两个端点相同，则称的两个端点相同，则称e是环。如是环。如 e7v1v2v3v4e1e2e3e4e5e6e7 多重边多重边若两个点之间有多于一条的边，称这些边为多重边。如若两个点之间有多于一条的边，称这些边为多重边。如 e1,e2 简单图简单图一个无环、无多重边的图。一个无环、无多重边的图。多重图多重图一个无环、但允许有多重边的图。一个无环、但允许有多重边的图。v1v2v3v4v1v2v3v416 点的次

14、点的次以点以点vi 为端点边的个数，为端点边的个数，记为记为dG(vi)或或d(vi)。v1v2v3v4e1e2e3e4e5e6e7如如 d(v4)=5 d(v2)=4v5 悬挂点悬挂点：次为：次为1 1的点，的点，如如 v5 悬挂边：悬挂边：悬挂点的关联边，悬挂点的关联边，如如 e8e8 孤立点：孤立点：次次为为0 0的点的点 偶点：偶点：次为偶数的点，次为偶数的点，如如 v2 奇点：奇点：次次为为奇数的点奇数的点,如如 v4v617 链链 中间点中间点 初等链初等链 圈圈 初等圈初等圈 简单圈简单圈 简单链简单链v1v2v5v6v7v3v4e1e2e4e3e5e6e7e8e9 在上图中在上

15、图中,(v1,v2,v3,v4,v5,v3,v6,v7)是一条链是一条链,但不是初等链但不是初等链在该链在该链中中,v2,v3,v4,v5,v3,v6是中间点是中间点(v1,v2,v3,v6,v7)是一条初等链是一条初等链(v1,v2,v3,v4,v1)是一个初等圈是一个初等圈(v4,v1,v2,v3,v5,v7,v6,v3,v4)是一个简单圈是一个简单圈点边交错序列点边交错序列链链18 连通图连通图 图图G中，若任何两个点之间，至少有一条链，称为连通图。中，若任何两个点之间，至少有一条链，称为连通图。否则称为不连通图。否则称为不连通图。连通分图连通分图(分图分图)若若G是不连通图，则它的每个

16、连通的部分称为连通分图。是不连通图，则它的每个连通的部分称为连通分图。v1v2v3v4e1e2e3e4e5e6v5v6e7如左图就是个不连通图，它如左图就是个不连通图，它是由两个连通分图构成的。是由两个连通分图构成的。19 支撑子图支撑子图给定一个图给定一个图G=(V,E)，如果图如果图G=(V,E)，使，使V=V 及及E E，则称则称G是是G的一个支撑子图。的一个支撑子图。v4v1v2v3(G)v1v2v3v4(G)基础图基础图给定一个有向图给定一个有向图D=(V,A)，从，从D中去掉所有弧上的箭头，所得到中去掉所有弧上的箭头，所得到的无向图称为基础图的无向图称为基础图。记之为记之为G(D)

17、。v1v2v3v4a1a2a3a4a5a6D=(V,A)v1v2v3v4e1e2e3e4e5e6G(D)20v1v2v3v4a1a2a3a4a5a6a7a8a9a10a11v6v7 路路 初等路初等路 回路回路 v5有向图有向图D中的点弧交错序列中的点弧交错序列链链21 简单有向图简单有向图v2v1v2v1v1v2v3v4a1a2a3a5a6a4v1v2v3v4a1a2a3a5a6a4G-vG-v一个无环，无多重弧的有向图一个无环，无多重弧的有向图一个无环，但允许有多重弧的有向图一个无环，但允许有多重弧的有向图多重有向图多重有向图从图从图G G中去掉点中去掉点v v以及点以及点v v的关联边的

18、关联边。G-v1v1v2v3v4e1e2e3e4e5e622 定理定理1 1 图图G=(V,E)中，所有点的次之和是边数的两倍，即中，所有点的次之和是边数的两倍，即 定理定理2 2 任一图中奇点的个数为偶数。任一图中奇点的个数为偶数。三、基本定理三、基本定理v1v2v3v4e1e2e3e4e5e6d(v1)=3d(v4)=3d(v2)=4d(v3)=2图图G或或D中点的个数：中点的个数：p(G)p(D)图图G或或D中边（弧）的条数：中边（弧）的条数：q(G)q(D)23一、定义：一、定义：无圈的连通图无圈的连通图例例1 1 在五个城市之间架设电话线，要求任两个城市之间都可在五个城市之间架设电话

19、线，要求任两个城市之间都可以相互通话（允许通过其他城市），并且电话线的根数最少。以相互通话（允许通过其他城市），并且电话线的根数最少。v1v5v2v3v4用用v1,v2,v3,v4,v5代表五个城市代表五个城市,如果在某两个城市之间架设电如果在某两个城市之间架设电话线话线,则在相应的两点之间联一则在相应的两点之间联一条边条边,这样一个电话线网就可以这样一个电话线网就可以用一个图来表示。显然用一个图来表示。显然,这个图这个图必须是连通的必须是连通的,而且是不含圈的而且是不含圈的连通图。如左图所示。连通图。如左图所示。第二节第二节 树树一个无圈的连通图称为树一个无圈的连通图称为树24例例2 2 某

20、工厂的组织机构如下图所示某工厂的组织机构如下图所示厂厂长长行行政政办办公公室室生生产产办办公公室室生产计划科生产计划科技术科技术科设计组设计组工艺组工艺组供销科供销科财务科财务科行政科行政科一车间一车间铸造工段铸造工段锻压工段锻压工段二二车间车间三车间三车间四车间四车间该厂的该厂的组织机构图就是一个树。组织机构图就是一个树。25例例3 3 树图树图倒置的树，根倒置的树，根(root)在上，叶在上，叶(leaf)在下在下26汽车评价汽车评价定量指标定量指标定性指标定性指标底底盘盘价价格格最最高高时时速速操操作作性性舒舒适适性性平平均均油油耗耗刹刹车车安安全全性性高高速速稳稳定定性性座座椅椅档档位

21、位27定理定理1 1 设图设图G=(V,E)是一个树，是一个树，p(G)2 G中至少有两个悬挂点中至少有两个悬挂点二、性质二、性质证明：证明：设设P=(v1,v2,vk)是是G中含边数最多的一条初等链，因中含边数最多的一条初等链，因p(G)2，并且，并且G是连通的，故链是连通的，故链P中至少有一条边，从而中至少有一条边，从而v1与与vk是不同的。下面证明是不同的。下面证明v1是悬挂点，即是悬挂点，即d(v1)=1。（反证法）。（反证法）假设假设d(v1)2，则存在边，则存在边v1,vm，使，使m2。（i）若点）若点vm在在P上，则上，则(v1,v2,vm,v1)是是G中的一个圈，这与中的一个圈

22、，这与树的定义矛盾。树的定义矛盾。（ii）若点）若点vm不在不在P上，则上，则(vm,v1,v2,vk)是是G中的一条初等链，中的一条初等链，它的边数比它的边数比P多一条，这与多一条，这与P是边数最多的初等链矛盾。是边数最多的初等链矛盾。故原假设不成立，于是故原假设不成立，于是d(v1)=1，即，即v1是悬挂点。同理可证是悬挂点。同理可证vk也也是悬挂点，故是悬挂点，故G至少有两个悬挂点。至少有两个悬挂点。28定理定理2 2 图图G=(V,E)是一个树是一个树 G中不含圈，且恰中不含圈，且恰有有p-1条边条边证明证明q q(G(G)=p(G)-1=n-1)=p(G)-1=n-1(要证明：当要证

23、明：当p(Gp(G)=n+1)=n+1 时，时，q(Gq(G)=n)=n)先证必要性。先证必要性。即要证明如果即要证明如果G G是树，那么是树，那么G G不含圈，且不含圈，且q(Gq(G)=p-1)=p-1用数学归纳法用数学归纳法当当p(Gp(G)=1,)=1,p(Gp(G)=2)=2时，显然成立时，显然成立设设p(Gp(G)=n)=n时，命题成立时，命题成立即当即当G G是树且含有是树且含有n n个点时，有个点时，有n-1n-1条边条边当当p(Gp(G)=n+1)=n+1时，由定理时，由定理1 1，G G中含有悬挂点，记为中含有悬挂点，记为v1 1因为因为G-G-v1 1是是n n个点的树，

24、个点的树，即即p(G-p(G-v1 1)=n)=n，由题设，由题设 q(G-q(G-v1 1)=n-1)=n-1又因为又因为G-G-v1 1是从是从G G中去掉中去掉v1 1以及以及v1 1的关联边的树的关联边的树所以所以 q(G-q(G-v1 1)=q(G)-1)=q(G)-1所以所以 q(G)-1=n-1 q(G)-1=n-1 q(Gq(G)=n)=n q(Gq(G)=p(G)-1)=p(G)-129如果图如果图G G不含圈，并且不含圈，并且q q(G(G)=p(G)-1)=p(G)-1，那么，那么G G是一个树是一个树s230定理定理3 3 图图G=(V,E)是一个树是一个树 G是连通图

25、，并且是连通图，并且q(G)=p(G)-1。证明证明 由定理由定理2，必要性显然。，必要性显然。当图当图G G有有n n个点且边数比点个点且边数比点数少数少1 1时不含圈时不含圈现要证明当图现要证明当图G G含有含有n+1个点且边数比点个点且边数比点数少数少1 1时也不含圈时也不含圈假设图假设图G G中有一个悬挂点，中有一个悬挂点，只要证明只要证明G-vG-v1 1不含圈，就不含圈，就证明了证明了G G中不含圈中不含圈也不含圈。也不含圈。不含圈，于是不含圈，于是因此由归纳假设知因此由归纳假设知GvG1-vqGqnG111)()(-=-=-vv 也是连通的。也是连通的。的一个悬挂点，则图的一个悬

26、挂点，则图是是设设GG11-p(G-v1)=p(G)-1=n31定理定理4 4 图图G是树的充分必要条件是是树的充分必要条件是 任意两个顶点之间恰有一条链。任意两个顶点之间恰有一条链。证明：证明：必要性证明：必要性证明：因为树是连通的，所以任意两点之间肯定有因为树是连通的，所以任意两点之间肯定有1条链；条链；其次，如果某两点之间有其次，如果某两点之间有2条链的话，那么图中肯定条链的话，那么图中肯定含有圈，这与树的定义相矛盾。含有圈，这与树的定义相矛盾。充分性证明：充分性证明：因为任两个顶点间恰有一条链，显然因为任两个顶点间恰有一条链，显然G是连通的。是连通的。如果如果G中含有圈的话，则其中至少

27、有两个顶点间有中含有圈的话，则其中至少有两个顶点间有两条链，这与题设矛盾。充分性得证。两条链，这与题设矛盾。充分性得证。推论：推论：从一个树中去掉一条边，则余下的图是不连通的。从一个树中去掉一条边，则余下的图是不连通的。在树中不相邻的两个点间添上一条边，则恰好得到一个圈。在树中不相邻的两个点间添上一条边，则恰好得到一个圈。v1v2v3v4（1 1）证明连通；（）证明连通；（2 2）证明无圈）证明无圈32v1v5v2v3v433三、图的支撑树三、图的支撑树定义：定义：设图设图T=(V,E)是图是图G的支撑子图，如果图的支撑子图，如果图T=(V,E)是一个树，则称是一个树，则称T是是G的一个支撑树

28、的一个支撑树。定理：定理：图图G有支撑树的充分必要条件是图有支撑树的充分必要条件是图G是连通的。是连通的。证明：证明：必要性显然。必要性显然。再证充分性。再证充分性。设图设图G是连通图，若是连通图，若G不含圈，则不含圈，则G本身本身是一个树，从而是一个树，从而G是它自身的一个支撑树是它自身的一个支撑树。如果如果G含圈，任取一个圈，从圈中任意地去掉一条边，得含圈，任取一个圈，从圈中任意地去掉一条边，得到图到图G的一个支撑子图的一个支撑子图G1。如果如果G1不含圈，那么不含圈，那么G1是是G的一个的一个支撑树；如果支撑树；如果G1仍含圈，那么从仍含圈，那么从G1中任取一个圈，从圈中再中任取一个圈，

29、从圈中再任意去掉一条边，得到图任意去掉一条边，得到图G的一个支撑子图的一个支撑子图G2，如此重复，最如此重复，最终可以得到终可以得到G的一个支撑子图的一个支撑子图Gk,它不含圈，于是它不含圈，于是Gk是是G的一的一个支撑树。个支撑树。34 破圈法破圈法例例 用破圈法求解图的一个支撑树用破圈法求解图的一个支撑树v1v2v3v4v5e1e2e3e4e5e6e7e8这就这就得到了该图的一个支撑树。得到了该图的一个支撑树。支撑树的求解方法支撑树的求解方法35 避圈法避圈法v1v2v3v4v5v6e1e2e3e4e5e6e7e8e9这就这就得到了该图的一个支撑树。得到了该图的一个支撑树。36定义定义1

30、1 给定图给定图G=(V,E)，对对G中的每一条边中的每一条边vi,vj，相应地相应地有一个数有一个数wij，则称图则称图G为赋权图，为赋权图，wij称为边称为边vi,vj上的权。上的权。1.1.定义定义定义定义2 2 如果如果T=(V,E)是是G的一个支撑树，称的一个支撑树，称E中所有边的中所有边的权之和为支撑树权之和为支撑树T的权，记为的权，记为w(T)，即即最小支撑树最小支撑树：如果支撑树如果支撑树T*的权的权w(T*)是是G的所有支撑树的权的所有支撑树的权中最小者，则称中最小者，则称T*是是G的最小支撑树的最小支撑树(简称最小树简称最小树),即即四、最小支撑树四、最小支撑树最小支撑树最

31、小支撑树问题问题37v1v2v3v4v1v2v3v4v1v2v3v4v1v2v3v4v1v2v3v4v1v2v3v4v1v2v3v4v1v2v3v4123456v1v2v3v4v1v2v3v4v1v2v3v4382.2.最小支撑树的求法最小支撑树的求法方法一：避圈法方法一：避圈法 开始选一条权最小的边，以后每一步中，总从未被选取的开始选一条权最小的边，以后每一步中，总从未被选取的边中选一条权最小的边，并使之与已选取的边不构成圈。边中选一条权最小的边，并使之与已选取的边不构成圈。v1v2v3v4v5v6651572344这就这就得到了该图的一个最小支撑树。得到了该图的一个最小支撑树。39方法二：

32、破圈法方法二：破圈法 任取一个圈，从圈中去掉一条权最大的边。在余下的图中，任取一个圈，从圈中去掉一条权最大的边。在余下的图中，重复这个步骤，直到得到不含圈的图为止，这时的图便是最重复这个步骤，直到得到不含圈的图为止，这时的图便是最小树。小树。v1v2v3v4v5v6651572344这就这就得到了该图的一个最小支撑树。得到了该图的一个最小支撑树。40第三节第三节 最短路问题最短路问题北京北京天津天津济南济南青岛青岛合肥合肥南京南京上海上海郑州郑州连云港连云港徐州徐州石家庄石家庄武汉武汉41第三节第三节 最短路问题最短路问题一、最短路问题的提出一、最短路问题的提出v1v2v3v4v5v6v7v8

33、v9132216610410423236例例1 1左图为单行线交左图为单行线交通网，弧旁数字通网，弧旁数字表示通过这条单表示通过这条单行线所需要的费行线所需要的费用。求从用。求从v1出发出发到到v8总费用最小总费用最小的路线。的路线。(v1,v3,v2,v5,v8)(v1,v4,v6,v7,v8)3+2+1+6=121+10+2+4=17(v1,v4,v6,v5,v4,v6,v7,v8)1+10+10+6+10+2+4=4342D=(V,A)a=(vi,vj)w(a)=wijvs vtP：从起点到终点的路从起点到终点的路w(P)：路路P中所有弧的权之和中所有弧的权之和v1v2v3v4v5v6v

34、713221661041042236v8v9最短路问题：最短路问题：在所有从起点到终点的路中，在所有从起点到终点的路中，寻求权最小的路。寻求权最小的路。P0w(P0)=d(vs,vt)从从vs到到vt的距离的距离43 若若P P是从是从v vs s到到v vj j的最短路，那么从的最短路，那么从v vs s到到P P上的任意一点的上的任意一点的最短路，就是从最短路，就是从v vs s沿着路沿着路P P到达该点的路。到达该点的路。vsvjviQPd1d1d1+d(vi,vj)d1+d(vi,vj)如果如果d1 d144二、求解方法二、求解方法 情形一：情形一：所有的权均为非负所有的权均为非负（w

35、ij0）寻找起点已标号而终点未标号的最小值寻找起点已标号而终点未标号的最小值(0,0)(v1,1)第一步：第一步：v1v2v3v4v5v6v7v8v9132216610410423236狄克斯特拉狄克斯特拉方方法法(Dijkstra,1959)P(v4)=1P(v1)=0S1=v1,v4,(v4)=1minP(v1)+12,P(v1)+13,P(v1)+14T T标号标号P P标号标号45v1v2v3v4v5v6v7v8v9132216610410423236(0,0)(v1,3)(v1,1)第二步：第二步：minP(v1)+12,P(v1)+13,P(v4)+46P(v3)=3S2=v1,v

36、4,v3,(v3)=146第三步：第三步：v1v2v3v4v5v6v7v8v9132216610410423236(0,0)(v1,3)(v1,1)(v3,5)minP(v1)+12,P(v3)+32,P(v4)+46P(v2)=5S3=v1,v4,v3,v2,(v2)=347第四步：第四步：v1v2v3v4v5v6v7v8v9132216610410423236(0,0)(v1,3)(v1,1)(v3,5)(v2,6)minP(v2)+25,P(v4)+46P(v5)=6S4=v1,v4,v3,v2,v5,(v5)=248第五步：第五步：(v5,9)v1v2v3v4v5v6v7v8v9132

37、216610410423236(0,0)(v1,3)(v1,1)(v3,5)(v2,6)minP(v5)+56,P(v5)+57,P(v5)+58,P(v4)+46P(v7)=9S5=v1,v4,v3,v2,v5,v7,(v7)=549第六步：第六步：(v5,9)v1v2v3v4v5v6v7v8v9132216610410423236(0,0)(v1,3)(v1,1)(v3,5)(v2,6)(v5,10)minP(v5)+56,P(v5)+58,P(v7)+78,P(v4)+46P(v6)=10S6=v1,v4,v3,v2,v5,v7,v6,(v6)=550第七步：第七步：(v5,12)(v5

38、,9)v1v2v3v4v5v6v7v8v9132216610410423236(0,0)(v1,3)(v1,1)(v3,5)(v2,6)(v5,10)minP(v7)+78,P(v5)+58 P(v8)=12S7=v1,v4,v3,v2,v5,v7,v6,v8,(v8)=551v1到到v8的最短路为的最短路为(v1,v3,v2,v5,v8),其长度为其长度为12.v1v2v3v4v5v6v7v8v9132216610410423236(v1,1)(v4,11)(v5,10)(v5,9)优点：优点：能找出从能找出从v1到所有点的最短路到所有点的最短路缺点：缺点：不能解决带有负权的图的最短路问题不

39、能解决带有负权的图的最短路问题(v5,12)(v2,6)(v3,5)(0,0)(v1,3)52狄克斯特拉狄克斯特拉方方法法的具体步骤的具体步骤 （wij0）在在运运算算过过程程中中，我我们们每每一一步步都都给给一一个个新新的的点点vj进进行行标标号号，标标号号分分为为两两部部分分，其其中中标标号号中中的的第第二二个个数数值值表表示示从从起起点点vs到到该该点点的的最最短短距距离离P(vj)，第第一一个个数数值值表表示示从从起起点点到到该该点点的的最最短短路路线线上上的的前前一一个个点点。用用(vj)表表示示从从vs到到vj的的最最短短路路线线上上vj的的前前一一个个点点的的下下标标。用用Si表

40、表示示进进行行到到第第i步步时，已经被标号的点的集合。时，已经被标号的点的集合。（1）给给起起点点vs标标号号(0,0)，并并令令S0=vs。标标号号中中的的第第二二个个数数值值P(vs)=0，表表示示从从起起点点到到该该点点的的最最短短距距离离为为0；由由于于是起点，因此标号中的第一个数值设为是起点，因此标号中的第一个数值设为0。53 寻寻找找从从vs发发出出的的所所有有弧弧，求求出出这这些些弧弧的的权权与与P(vs)之之和和的的最最小小值，即值，即 (j为从起点为从起点vs发出的所有弧的终点的下标发出的所有弧的终点的下标)对以上最小值所对应的点进行标号，并确定对以上最小值所对应的点进行标号

41、，并确定S1。（2）继继续续探探寻寻从从已已标标号号的的点点出出发发、终终点点为为未未标标号号点点的的弧弧，求求出出已已标标号号点点的的P值值与与相相应应弧弧的的权权之之和和，对对其其中中最最小小值值所所对对应应的点进行标号，并确定的点进行标号，并确定S2。（3）以以此此步步骤骤进进行行，直直到到找找不不到到从从已已标标号号点点出出发发、终终点点为为未未标号点的弧时，就得到了从起点标号点的弧时，就得到了从起点vs到各个点的最短距离。到各个点的最短距离。如如果果最最后后标标号号进进行行不不下下去去时时还还存存在在未未标标号号的的点点，则则意意味味着着从从起起点点vs不存在到达该点的路线。不存在到

42、达该点的路线。（4）利用逆向思维，可以找到从起点到任何一点的最短路线。）利用逆向思维，可以找到从起点到任何一点的最短路线。54情形二：赋权有向图中存在具有负权的弧情形二：赋权有向图中存在具有负权的弧v1v2v3v4v5v6v7v8例例2 2 求求 v1 到图中其他各点的最短路。到图中其他各点的最短路。6-1-283-3-5-121112-1-3-57d(t)(vs,vj)在在第第 t 轮轮，由由vs到到vj 的的临临时时最短距离最短距离不妨设从任一点不妨设从任一点vi到任一点到任一点vj都有一都有一条弧（如果在条弧（如果在D中，中，(vi,vj)A，添加，添加弧弧(vi,vj)，令，令wij=

43、+）55情形二：赋权有向图中存在具有负权的弧情形二：赋权有向图中存在具有负权的弧v1v2v3v4v5v6v7v8例例2 2 求求 v1 到图中其他各点的最短路。到图中其他各点的最短路。6-1-283-3-5-121112-1-3-57(0,0)(v1,-1)(v1,3)(v1,-2)(v1,)(v1,)(v1,)(v1,)d(1)(v1,v1)=11=0d(1)(v1,v2)=12=-1d(1)(v1,v3)=13=-2d(1)(v1,v4)=14=3d(1)(v1,v5)=15=d(1)(v1,v6)=16=d(1)(v1,v7)=17=d(1)(v1,v8)=18=d(1)(vs,vj)=

44、sj56v1v2v3v4v5v6v7v86-1-283-3-5-121112-1-3-57(0,0)(v1,-1)(v1,3)(v1,-2)(v1,)(v1,)(v1,)(v1,)(v3,-5)(v3,-7)(v3,-1)(v4,5)(v2,1)d(1)(v1,v1)+12d(1)(v1,v2)+22d(1)(v1,v3)+32d(1)(v1,v4)+42d(1)(v1,v5)+52d(1)(v1,v6)+62d(1)(v1,v7)+72d(1)(v1,v8)+82d(2)(v1,v2)=Min57v1v2v3v4v5v6v7v86-1-283-3-5-121112-1-3-57(0,0)(v

45、1,-1)(v1,3)(v1,-2)(v1,)(v1,)(v3,-5)(v3,-7)(v3,-1)(v2,1)(v4,5)(v6,6)(v2,-3)(v4,-5)58v1v2v3v4v5v6v7v86-1-283-3-5-121112-1-3-57(0,0)(v1,-1)(v1,3)(v1,-2)(v1,)(v1,)(v1,)(v1,)(v3,-5)(v3,-7)(v3,-1)(v2,-3)(v4,-5)(v6,6)(v5,-4)(v7,-6)(v8,3)(v8,1)59wijd(t)(v1,vj)v1v2v3v4v5v6v7v8t=1t=2t=3t=4v10-1-230000v2602-1-

46、5-5-5v3-30-51-2-2-2-2v48023-7-7-7v5-101-3-3v61017-1-1-1v7-105-5-5v8-3-5066说明：说明：表中空格处为表中空格处为+。缺点：缺点：不能解决不能解决负回路负回路的情况。的情况。60(v1,v2,v3,v1)v1v2v3-52161 给每一个点一个标号，标号由两部分组成。后一部给每一个点一个标号，标号由两部分组成。后一部分表示从起点到该点的临时最短距离；前一部分表示分表示从起点到该点的临时最短距离；前一部分表示从起点到该点的临时最短路线上的前一点。从起点到该点的临时最短路线上的前一点。我们每进行一轮，都去修改标号中的值，直到进行

47、我们每进行一轮，都去修改标号中的值，直到进行到某一轮，所有标号中的值都不发生变化了，就得到到某一轮，所有标号中的值都不发生变化了，就得到了起点到各个点的最短距离和最短路线。了起点到各个点的最短距离和最短路线。在在这这里里，设设d(t)(vs,vj)为为第第t轮轮由由起起点点vs到到点点vj的的临临时时最最短距离。短距离。（1）令第）令第1轮的临时最短距离为：轮的临时最短距离为：d(1)(vs,vj)=sj；（2）求求解解第第2轮轮中中从从起起点点vs到到点点vj的的临临时时最最短短距距离离d(2)(vs,vj)。对于点对于点vj，计算，计算d(2)(vs,vj)=minid(1)(vs,vi)

48、+ij 具有负权的最短路算法具有负权的最短路算法62 设在第设在第t轮中从起点轮中从起点vs到点到点vj的临时最短距离为的临时最短距离为d(t)(vs,vj)，则对于点，则对于点vj，有，有d(t)(vs,vj)=minid(t-1)(vs,vi)+ij 当当进进行行到到第第k轮轮时时，所所有有点点的的标标号号经经过过计计算算都都不不再再发发生变化时，即生变化时，即d(k)(vs,vj)=d(k-1)(vs,vj)就得到了起点就得到了起点vs到各点的最短距离。到各点的最短距离。从从vs到到vj可以分两步走，第一步，先从可以分两步走，第一步，先从vs到到vi，第二步，第二步，从从vi到到vj。因

49、此，假如一个图有。因此，假如一个图有n个点，对每一个点就有个点，对每一个点就有n种路线可选择，我们在这种路线可选择，我们在这n种路线中找出距离最短的作为种路线中找出距离最短的作为该点的临时最短距离。该点的临时最短距离。由由于于当当vi和和vj之之间间不不存存在在弧弧时时，ij=，因因此此我我们们只只需需找找出出终终点点在在该该点点的的所所有有弧弧，用用所所有有弧弧的的弧弧长长加加上上这这些些弧弧的的起起点点的的临临时时最最短短距距离离，其其中中的的最最小小者者如如果果比比该该点点的的标标号号值值小小，就设为该点新的临时最短距离。就设为该点新的临时最短距离。63三、应用举例三、应用举例 例例3

50、3 设备更新问题。某企业使用一台设备，在每年年初设备更新问题。某企业使用一台设备，在每年年初都要决定是购置新设备还是继续使用旧的。购置新设备要都要决定是购置新设备还是继续使用旧的。购置新设备要支付一定的购置费，使用旧设备则要支付维修费。试制定支付一定的购置费，使用旧设备则要支付维修费。试制定一个五年的设备更新计划，使得总支付费用最少。一个五年的设备更新计划，使得总支付费用最少。已知该设备在各年年初的价格为：已知该设备在各年年初的价格为：第一年第一年第二年第二年第三年第三年第四年第四年第五年第五年1111121213已知使用不同时间的设备维修费用为：已知使用不同时间的设备维修费用为：使用年数使用