第六章图与网络规划PPT讲稿.ppt

《第六章图与网络规划PPT讲稿.ppt》由会员分享，可在线阅读，更多相关《第六章图与网络规划PPT讲稿.ppt（152页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第六章图与网络规划第六章图与网络规划第1页，共152页，编辑于2022年，星期三Chapter6 图与网络分析图与网络分析(Graph Theory and Network Analysis)(Graph Theory and Network Analysis)图的基本概念与模型图的基本概念与模型树与图的最小树树与图的最小树最短路问题最短路问题网络的最大流网络的最大流最小费用最大流最小费用最大流本章主要内容：本章主要内容：本章主要内容：本章主要内容：第2页，共152页，编辑于2022年，星期三近代图论的历史可追溯到近代图论的历史可追溯到18世纪的七桥问题世纪的七桥问题穿过穿过Knigsberg

2、城的城的七座桥，要求每座桥通过一次且仅通过一次。七座桥，要求每座桥通过一次且仅通过一次。这就是著名的这就是著名的“哥尼斯堡哥尼斯堡 7 桥桥”难题。难题。Euler1736年证明了不可能存在这样的路线。年证明了不可能存在这样的路线。图的基本概念与模型图的基本概念与模型KnigsbergKnigsberg桥对应的图桥对应的图第3页，共152页，编辑于2022年，星期三图的基本概念与模型图的基本概念与模型图论中图是由点和边构成，可以反映一些对象之间的关系。图论中图是由点和边构成，可以反映一些对象之间的关系。一般情况下图中点的相对位置如何、点与点之间联线的长短一般情况下图中点的相对位置如何、点与点之

3、间联线的长短曲直，对于反映对象之间的关系并不是重要的。曲直，对于反映对象之间的关系并不是重要的。图的定义：图的定义：图的定义：图的定义：若用点表示研究的对象，用边表示这些对象之间的联系，则图若用点表示研究的对象，用边表示这些对象之间的联系，则图G可以定义为点和边的集合，记作：可以定义为点和边的集合，记作：其中其中:V点集点集 E边集边集 图图G区别于几何学中的图。这里只关心图中有多少个点以及哪些区别于几何学中的图。这里只关心图中有多少个点以及哪些点之间有连线。点之间有连线。第4页，共152页，编辑于2022年，星期三图的基本概念与模型图的基本概念与模型(v1)赵赵(v2)钱钱孙孙(v3)李李(

4、v4)周周(v5)吴吴(v6)陈陈(v7)e2e1e3e4e5(v1)赵赵(v2)钱钱(v3)孙孙(v4)李李(v5)周周(v6)吴吴(v7)陈陈e2e1e3e4e5可见图论中的图与几何图、工程图是不一样的。可见图论中的图与几何图、工程图是不一样的。例如：在一个人群中，对相互认识这个关系我们可以用图来表示。例如：在一个人群中，对相互认识这个关系我们可以用图来表示。第5页，共152页，编辑于2022年，星期三图的基本概念与模型图的基本概念与模型定义定义:图中的点用图中的点用v表示，边用表示，边用e表示。对每条边可用它所连表示。对每条边可用它所连接的点表示，记作：接的点表示，记作：e1=v1,v1

5、;e2=v1,v2;v3e7e4e8e5e6e1e2e3v1v2v4v5 端点端点,关联边关联边,相邻相邻若有边若有边e可表示为可表示为e=vi,vj，称，称vi和和vj是边是边e的的端点端点，反之称边，反之称边e为点为点vi或或vj的的关联关联边边。若点。若点vi、vj与同一条边关联，称点与同一条边关联，称点vi和和vj相邻；若边相邻；若边ei和和ej具有公共的端点，具有公共的端点，称边称边ei和和ej相邻相邻。第6页，共152页，编辑于2022年，星期三图的基本概念与模型图的基本概念与模型 环环,多重边多重边,简单图简单图如果边如果边e的两个端点相重，称该边为的两个端点相重，称该边为环环。

6、如右图中边如右图中边e1为环。如果两个点之间多于为环。如果两个点之间多于一条，称为一条，称为多重边多重边，如右图中的，如右图中的e4和和e5，对无环、无多重边的图称作对无环、无多重边的图称作简单图简单图。v3e7e4e8e5e6e1e2e3v1v2v4v5第7页，共152页，编辑于2022年，星期三图的基本概念与模型图的基本概念与模型 次，奇点，偶点，孤立点次，奇点，偶点，孤立点与某一个点与某一个点vi相关联的边的数目称为点相关联的边的数目称为点vi的的次次（也叫做度），记作（也叫做度），记作d(vi)。右图中。右图中d(v1),d(v3)=5,d(v5)=1。次为奇数的。次为奇数的点称作点称

7、作奇点奇点，次为偶数的点称作，次为偶数的点称作偶点偶点，次，次为为1的点称为的点称为悬挂点悬挂点，次为，次为0的点称作的点称作孤立孤立点点。v3e7e4e8e5e6e1e2e3v1v2v4v5图的次图的次:一个图的次等于各点的次之和。一个图的次等于各点的次之和。第8页，共152页，编辑于2022年，星期三图的基本概念与模型图的基本概念与模型 链，圈，连通图链，圈，连通图图中某些点和边的交替序列，若其中各图中某些点和边的交替序列，若其中各边互不相同，且对任意边互不相同，且对任意vi,t-1和和vit均相邻均相邻称为称为链链。用。用 表示：表示：v3e7e4e8e5e6e1e2e3v1v2v4v5

8、起点与终点重合的链称作起点与终点重合的链称作圈圈。如果。如果每一对顶点之间至少存在一条链，每一对顶点之间至少存在一条链，称这样的图为称这样的图为连通图连通图，否则称图不连，否则称图不连通。通。第9页，共152页，编辑于2022年，星期三图的基本概念与模型图的基本概念与模型 二部图（偶图）二部图（偶图）图图G=(V,E)的点集的点集V可以分为两个非空子集可以分为两个非空子集X，Y，集，集XY=V,XY=,使得同一集合中任意两个顶点均不相邻，使得同一集合中任意两个顶点均不相邻，称这样的图为偶图。称这样的图为偶图。v1v3v5v2v4v6v1v2v3v4v1v4v2v3(a)(b)(c)(a)明显为

9、二部图，明显为二部图，(b)也是二部图，但不明显，改画为也是二部图，但不明显，改画为(c)时可以清时可以清楚看出。楚看出。第10页，共152页，编辑于2022年，星期三图的基本概念与模型图的基本概念与模型 子图，部分图子图，部分图(支撑子图支撑子图)图图G1=V1、E1和图和图G2=V2，E2如果有如果有 称称G1是是G2的一个的一个子图子图。若。若有有 ，则称，则称G1是是G2的一个的一个部分部分图图(支撑子图支撑子图)。v3e7e4e8e5e6e1e2e3v1v2v4v5v3e4e8e5e6v2v4v5v3e7e4e8e6e2e3v1v2v4v5(a)(b)（G图）图）第11页，共152页

10、，编辑于2022年，星期三图的基本概念与模型图的基本概念与模型 网络（赋权图）网络（赋权图）设图设图G（V，E），对），对G的每一条边的每一条边(vi,vj)相应赋予数量指标相应赋予数量指标wij，wij称为边称为边(vi,vj)的的权权,赋予权的图赋予权的图G称为网络称为网络(或或赋权图）赋权图）。权可以代表距离、费用、通过能力权可以代表距离、费用、通过能力(容量容量)等等。等等。端点无序的赋权图称为端点无序的赋权图称为无向网络无向网络，端点有序的赋权图称为，端点有序的赋权图称为有向网络。有向网络。910201571419256第12页，共152页，编辑于2022年，星期三图的基本概念与模型

11、图的基本概念与模型 出次与入次出次与入次 有有向向图图中中，以以vi为为始始点点的的边边数数称称为为点点vi的的出出次次，用用d+(vi)表表示示；以以vi为为终终点点的的边边数数称称为为点点vi 的的入入次次，用用表表示示d-(vi)；vi 点点的的出出次次和和入入次之和就是该点的次。次之和就是该点的次。有向图中，所有顶点的入次之和等于所有顶点的出次之和。有向图中，所有顶点的入次之和等于所有顶点的出次之和。第13页，共152页，编辑于2022年，星期三图的基本概念与模型图的基本概念与模型图的模型应用图的模型应用图的模型应用图的模型应用例例6.1 有甲有甲,乙乙,丙丙,丁丁,戊戊,己己6名运动

12、员报名参加名运动员报名参加A,B,C,D,E,F 6个项个项目的比赛。下表中打目的比赛。下表中打的是各运动员报告参加的比赛项目。问的是各运动员报告参加的比赛项目。问6个个项目的比赛顺序应如何安排，做到每名运动员都不连续地参加两项目的比赛顺序应如何安排，做到每名运动员都不连续地参加两项比赛。项比赛。ABCDEF甲乙丙丁戊己第14页，共152页，编辑于2022年，星期三图的基本概念与模型图的基本概念与模型解：用图来建模。把比赛项目作为研究对象，用点表示。如解：用图来建模。把比赛项目作为研究对象，用点表示。如果果2个项目有同一名运动员参加，在代表这两个项目的点之个项目有同一名运动员参加，在代表这两个

13、项目的点之间连一条线，可得下图。间连一条线，可得下图。ABCDEF在图中找到一个点序列，在图中找到一个点序列，使得依次排列的两点不使得依次排列的两点不相邻，即能满足要求。相邻，即能满足要求。如：如：1)A,C,B,F,E,D2)D,E,F,B,C,A第15页，共152页，编辑于2022年，星期三图的基本概念与模型图的基本概念与模型一一个个班班级级的的学学生生共共计计选选修修A、B、C、D、E、F六六门门课课程程，其其中中一一部部分分人人同同时时选选修修D、C、A，一一部部分分人人同同时时选选修修B、C、F，一一部部分分人人同同时时选选修修B、E，还还有有一一部部分分人人同同时时选选修修A、B，

14、期期终终考考试试要要求求每每天天考考一一门门课课，六六天天内内考考完完，为为了了减减轻轻学学生生负负担担，要要求求每每人人都都不不会会连连续续参参加加考考试，试设计一个考试日程表。试，试设计一个考试日程表。思考题思考题第16页，共152页，编辑于2022年，星期三图的基本概念与模型图的基本概念与模型思考题解答：思考题解答：思考题解答：思考题解答：以每门课程为一个顶点，共同被选修的课程之间用边以每门课程为一个顶点，共同被选修的课程之间用边相连，得图，按题意，相邻顶点对应课程不能连续考试，不相连，得图，按题意，相邻顶点对应课程不能连续考试，不相邻顶点对应课程允许连续考试。相邻顶点对应课程允许连续考

15、试。第17页，共152页，编辑于2022年，星期三图的基本概念与模型图的基本概念与模型A AF FE ED DC CB B第18页，共152页，编辑于2022年，星期三图的基本概念与模型图的基本概念与模型A AF FE ED DC CB B第19页，共152页，编辑于2022年，星期三图的基本概念与模型图的基本概念与模型图的基本性质：图的基本性质：图的基本性质：图的基本性质：定理定理1 任何图中，顶点次数之和等于所有边数的任何图中，顶点次数之和等于所有边数的2倍。倍。定理定理2 任何图中，次为奇数的顶点必为偶数个。任何图中，次为奇数的顶点必为偶数个。证明：由于每条边必与两个顶点关联，在计算点的

16、次时，每条边均被计算了两证明：由于每条边必与两个顶点关联，在计算点的次时，每条边均被计算了两次，所以顶点次数的总和等于边数的次，所以顶点次数的总和等于边数的2倍。倍。证明：设证明：设V1和和V2分别为图分别为图G中奇点与偶点的集合。由定理中奇点与偶点的集合。由定理1可得：可得：2m为偶数，且偶点的次之和为偶数，且偶点的次之和 也为偶数，所以也为偶数，所以 必为偶数，即奇数点的必为偶数，即奇数点的个数必为偶数。个数必为偶数。第20页，共152页，编辑于2022年，星期三图的基本概念与模型图的基本概念与模型图的矩阵描述：图的矩阵描述：如何在计算机中存储一个图呢？现在已有很多存储的方法，如何在计算机

17、中存储一个图呢？现在已有很多存储的方法，但最基本的方法就是采用矩阵来表示一个图，图的矩阵表示但最基本的方法就是采用矩阵来表示一个图，图的矩阵表示也根据所关心的问题不同而有：也根据所关心的问题不同而有：邻接矩阵、关联矩阵、权矩阵等。邻接矩阵、关联矩阵、权矩阵等。1.邻接矩阵邻接矩阵对于图对于图G=（V，E），），|V|=n，|E|=m，有，有n n阶方阶方矩阵矩阵A=(aij)n n，其中其中第21页，共152页，编辑于2022年，星期三图的基本概念与模型图的基本概念与模型v5v1v2v3v4v64332256437例例6.2 下图所表示的图可以构造邻接矩阵下图所表示的图可以构造邻接矩阵A如下如

18、下第22页，共152页，编辑于2022年，星期三对于赋权图对于赋权图G=(V,E),其中边其中边 有权有权 ,构造矩阵构造矩阵B=(bij)n n 其中：其中：图的基本概念与模型图的基本概念与模型2.2.关联矩阵关联矩阵关联矩阵关联矩阵对于图对于图G=(V,E),|V|=n,|E|=m,有有m n阶阶矩阵矩阵M=(mij)m n，其中其中:3.3.权矩阵权矩阵权矩阵权矩阵第23页，共152页，编辑于2022年，星期三图的基本概念与模型图的基本概念与模型1 0 1 0 0 0 0 0 0 0 0 01 1 0 0 1 0 0 0 0 0 0 00 1 0 0 0 1 1 1 0 0 0 00 0

19、 0 0 0 0 0 0 1 0 0 10 0 1 1 1 1 0 0 0 0 0 00 0 0 0 0 0 0 0 1 1 0 00 0 0 0 0 0 0 0 0 1 1 10 0 0 1 0 0 1 1 0 0 0 0v1v2v3v4v5v6v7v8e1 e2 e3 e4 e5 e6 e7 e8 e9 e10 e11 e12 v1v2v3v5v8v7e1e2e3e4e6e5e7e9e12e10e11e8v6v4例例6.3 下图所表示的图可以构造关联矩阵下图所表示的图可以构造关联矩阵M如下如下:M=（mij）=第24页，共152页，编辑于2022年，星期三图的基本概念与模型图的基本概念与模

20、型v5v1v2v3v4v64332256437例例6.4 下图所表示的图可以构造权矩阵下图所表示的图可以构造权矩阵B如下如下:第25页，共152页，编辑于2022年，星期三树与图的最小树树与图的最小树树是图论中结构最简单但又十分重要的图。在自然和社会领域应用树是图论中结构最简单但又十分重要的图。在自然和社会领域应用极为广泛。极为广泛。例例6.2 乒乓求单打比赛抽签后，可用图来表示相遇情况，如下乒乓求单打比赛抽签后，可用图来表示相遇情况，如下图所示。图所示。AB CDEF GH运动员运动员第26页，共152页，编辑于2022年，星期三树与图的最小树树与图的最小树例例6.3 某企业的组织机构图也可

21、用树图表示。某企业的组织机构图也可用树图表示。厂长厂长人事科人事科财务科财务科总工总工程师程师生产副生产副厂长厂长经营副经营副厂长厂长开发科开发科技术科技术科生产科生产科设备科设备科供应科供应科销售科销售科检验科检验科动力科动力科第27页，共152页，编辑于2022年，星期三树与图的最小树树与图的最小树 树：无圈的连通图即为树树：无圈的连通图即为树性质性质1：任何树中必存在次为：任何树中必存在次为1的点。的点。性质性质2：n 个顶点的树必有个顶点的树必有n-1 条边。条边。性质性质3：树中任意两个顶点之间，恰有且仅有一条链。：树中任意两个顶点之间，恰有且仅有一条链。性质性质4：树连通，但去掉任

22、一条边，必变为不连通。：树连通，但去掉任一条边，必变为不连通。性质性质5：树无回圈，但不相邻的两个点之间加一条边，恰得到一个圈。：树无回圈，但不相邻的两个点之间加一条边，恰得到一个圈。v1v2v3v4v5v6第28页，共152页，编辑于2022年，星期三树与图的最小树树与图的最小树 图的最小部分树图的最小部分树(支撑树支撑树)如果如果G2是是G1的部分图，又是树图，则称的部分图，又是树图，则称G2是是G1的部分树（或的部分树（或支撑树）。树图的各条边称为树枝，一般图支撑树）。树图的各条边称为树枝，一般图G1含有多个部分树，含有多个部分树，其中树枝总长最小的部分树，称为该图的最小部分树（或最小支

23、其中树枝总长最小的部分树，称为该图的最小部分树（或最小支撑树）。撑树）。v1v2v3v4v5v1v2v3v4v5G1G2第29页，共152页，编辑于2022年，星期三树与图的最小树树与图的最小树a ab bc cf fe ed dh hg gb bf fe ed d第30页，共152页，编辑于2022年，星期三树与图的最小树树与图的最小树a ab bc cf fe ed dh hg gb bf fd dg g第31页，共152页，编辑于2022年，星期三树与图的最小树树与图的最小树b bc ce ed da ab bc cf fe ed dh hg g第32页，共152页，编辑于2022年，星

24、期三树与图的最小树树与图的最小树a ab bc ch ha ab bc cf fe ed dh hg g第33页，共152页，编辑于2022年，星期三树与图的最小树树与图的最小树a af fd dg ga ab bc cf fe ed dh hg g第34页，共152页，编辑于2022年，星期三树与图的最小树树与图的最小树求树的方法：破圈法和避圈法求树的方法：破圈法和避圈法求树的方法：破圈法和避圈法求树的方法：破圈法和避圈法破圈法破圈法破圈法破圈法第35页，共152页，编辑于2022年，星期三树与图的最小树树与图的最小树部分树部分树第36页，共152页，编辑于2022年，星期三树与图的最小树树

25、与图的最小树避圈法避圈法避圈法避圈法v1v2v3v4v5v6v1v3v1v3v2v1v3v2v5v6v1v3v2v5v6v4v1v3v2v5第37页，共152页，编辑于2022年，星期三树与图的最小树树与图的最小树赋权图中求最小树的方法：破圈法和避圈法赋权图中求最小树的方法：破圈法和避圈法赋权图中求最小树的方法：破圈法和避圈法赋权图中求最小树的方法：破圈法和避圈法破圈法破圈法：任取一圈，去掉圈中最长边，直到无圈。：任取一圈，去掉圈中最长边，直到无圈。5v1v2v3v4v5v6843752618v1v2v3v4v5v643521边数边数n-1=5第38页，共152页，编辑于2022年，星期三树与

26、图的最小树树与图的最小树v1v2v3v4v5v643521得到最小树：得到最小树：Min C(T)=15第39页，共152页，编辑于2022年，星期三树与图的最小树树与图的最小树避圈法避圈法:去掉去掉G中所有边，得到中所有边，得到n个孤立点；然后加边。个孤立点；然后加边。加边的原则为：从最短边开始添加，加边的过程中不能形成加边的原则为：从最短边开始添加，加边的过程中不能形成圈，直到点点连通圈，直到点点连通(即即:n-1条边条边)。5v1v2v3v4v5v6843752618第40页，共152页，编辑于2022年，星期三树与图的最小树树与图的最小树v1v2v3v4v5v6435215v1v2v3

27、v4v5v6843752618Min C(T)=15第41页，共152页，编辑于2022年，星期三树与图的最小树树与图的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636练习：练习：练习：练习：应用破圈法求最小树应用破圈法求最小树应用破圈法求最小树应用破圈法求最小树第42页，共152页，编辑于2022年，星期三树与图的最小树树与图的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636第43页，共15

28、2页，编辑于2022年，星期三树与图的最小树树与图的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 12323第44页，共152页，编辑于2022年，星期三树与图的最小树树与图的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 12323第45页，共152页，编辑于2022年，星期三树与图的最小树树与图的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v615159 9161625253 3282817174 41 12

29、323第46页，共152页，编辑于2022年，星期三树与图的最小树树与图的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v615159 9161625253 3282817174 41 12323第47页，共152页，编辑于2022年，星期三树与图的最小树树与图的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v69 9161625253 3282817174 41 12323第48页，共152页，编辑于2022年，星期三树与图的最小树树与图的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v69 9161625253 3282817174 41 12323第4

30、9页，共152页，编辑于2022年，星期三树与图的最小树树与图的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v69 925253 3282817174 41 12323第50页，共152页，编辑于2022年，星期三树与图的最小树树与图的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v69 925253 3282817174 41 12323第51页，共152页，编辑于2022年，星期三树与图的最小树树与图的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v69 93 3282817174 41 12323第52页，共152页，编辑于2022年，星期三树与图的

31、最小树树与图的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v69 93 3282817174 41 12323第53页，共152页，编辑于2022年，星期三树与图的最小树树与图的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v69 93 317174 41 12323min=1+4+9+3+17+23=57第54页，共152页，编辑于2022年，星期三树与图的最小树树与图的最小树练习：练习：练习：练习：应用避圈法求最小树应用避圈法求最小树应用避圈法求最小树应用避圈法求最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253

32、 3282817174 41 123233636第55页，共152页，编辑于2022年，星期三树与图的最小树树与图的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636第56页，共152页，编辑于2022年，星期三树与图的最小树树与图的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636第57页，共152页，编辑于2022年，星期三树与图的最小树树与图的最小树v1v1v7v7v4v4v3v3v2v2v

33、5v5v6v6202015159 9161625253 3282817174 41 123233636第58页，共152页，编辑于2022年，星期三树与图的最小树树与图的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636第59页，共152页，编辑于2022年，星期三树与图的最小树树与图的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636第60页，共152页，编辑于2022年，星期三树与图的最小树树

34、与图的最小树v1v1v7v7v4v4v3v3v2v2v5v5v6v6202015159 9161625253 3282817174 41 123233636min=1+4+9+3+17+23=57min=1+4+9+3+17+23=57第61页，共152页，编辑于2022年，星期三树与图的最小树树与图的最小树课堂练习：课堂练习：课堂练习：课堂练习：3749346321Min C(T)=12Min C(T)=15254173314475答案：答案：第62页，共152页，编辑于2022年，星期三树与图的最小树树与图的最小树34122323242Min C(T)=122136385345674543

35、21Min C(T)=18第63页，共152页，编辑于2022年，星期三最短路问题最短路问题问题描述：问题描述：最短路问题是对一个赋权的有向图最短路问题是对一个赋权的有向图D=(V,A)，若，若D的每条的每条弧弧a=(vi,vj)都对应一个实数都对应一个实数(a)（称为（称为a的权），从图的权），从图D中指定两中指定两个点个点vs和和vt，找到一条从，找到一条从vs到到vt的路，使得这条路上所有的弧的权的路，使得这条路上所有的弧的权数数(a)的和最小，这条路称为的和最小，这条路称为vs到到vt的的最短路最短路，这条路上所有弧，这条路上所有弧的权数的和称为从的权数的和称为从vs到到vt的的距离距

36、离。很多管理问题，如选址、管道铺设时的选线、设备更新、很多管理问题，如选址、管道铺设时的选线、设备更新、投资、某些整数规划和动态规划的问题，都可以归结为求最短投资、某些整数规划和动态规划的问题，都可以归结为求最短路的问题。因此这类问题在生产实际中得到广泛应用。路的问题。因此这类问题在生产实际中得到广泛应用。第64页，共152页，编辑于2022年，星期三最短路问题最短路问题例例例例6.4 6.4 渡河游戏渡河游戏渡河游戏渡河游戏一老汉带了一只狼、一只羊、一棵白菜想要从南岸过一老汉带了一只狼、一只羊、一棵白菜想要从南岸过河到北岸，河上只有一条独木舟，每次除了人以外，只能带河到北岸，河上只有一条独木

37、舟，每次除了人以外，只能带一样东西；另外，如果人不在，狼就要吃羊，羊就要吃白菜，一样东西；另外，如果人不在，狼就要吃羊，羊就要吃白菜，问应该怎样安排渡河，才能做到既把所有东西都运过河去，问应该怎样安排渡河，才能做到既把所有东西都运过河去，并且在河上来回次数最少？这个问题就可以用求最短路方法并且在河上来回次数最少？这个问题就可以用求最短路方法解决。解决。第65页，共152页，编辑于2022年，星期三最短路问题最短路问题定义：定义：1）人）人M（Man），狼），狼W（Wolf），），羊羊G（Goat），），白菜白菜C（Cabbage）2）点点 vi 表示河岸的状态表示河岸的状态3）边边 ek 表示

38、由状态表示由状态 vi 经一次渡河到状态经一次渡河到状态 vj 4）权权边边 ek 上的权定为上的权定为 1我们可以得到下面的我们可以得到下面的赋赋权有向图权有向图第66页，共152页，编辑于2022年，星期三最短路问题最短路问题状态说明：状态说明：v1,u1=(M,W,G,C);v2,u2=(M,W,G);v3,u3=(M,W,C);v4,u4=(M,G,C);v5,u5=(M,G)此游戏转化为在下面的二部图中求从此游戏转化为在下面的二部图中求从 v1 到到 u1 的最短路问题。的最短路问题。v1v2v3v4v5u5u4u3u2u1第67页，共152页，编辑于2022年，星期三最短路问题最短

39、路问题求最短路有两种算法求最短路有两种算法:狄克斯屈拉（狄克斯屈拉（Dijkstra，又叫标号算法），又叫标号算法）矩阵算法（又叫矩阵算法（又叫Floyed算法）算法）第68页，共152页，编辑于2022年，星期三最短路问题最短路问题狄克斯屈拉狄克斯屈拉狄克斯屈拉狄克斯屈拉(Dijkstra)(Dijkstra)算法的基本思路：算法的基本思路：算法的基本思路：算法的基本思路：若序列若序列 vs,v1.vn-1,vt 是从是从vs到到vt间的最短路，则序列间的最短路，则序列 vs,v1.vn-1 必为从必为从vs 到到vn-1的最短路。的最短路。假定假定v1v2 v3 v4是是v1 v4的最短路

40、，则的最短路，则v1 v2 v3一定一定是是v1 v3的最短路，的最短路，v2 v3 v4也一定是也一定是v2 v4的最短路。的最短路。v1v2v3v4v5第69页，共152页，编辑于2022年，星期三最短路问题最短路问题求网络图的最短路，设图的起点是求网络图的最短路，设图的起点是vs,终点是终点是vt ,以以vi为起点为起点vj为终点的弧记为为终点的弧记为(i,j)距离为距离为dijP P标号标号标号标号(点标号点标号点标号点标号)：b(j)起点起点vs到点到点vj的最短路长；的最短路长；T T标号标号标号标号(边标号边标号边标号边标号)：k(i,j)=b(i)+dij，1.令起点的标号；令

41、起点的标号；b(s)0。2.记所有已标号的点记所有已标号的点vi 的集合为的集合为S，未标号的点的集合为，未标号的点的集合为P，如果从，如果从S到到P中不存在弧，或者中不存在弧，或者S已经包含已经包含vt，计算结束；，计算结束；3.计算从计算从S到到P的弧的弧k(i，j)=b(i)+dij的标号的标号4.选一个点标号选一个点标号 在终点在终点vl处标号处标号b(l),返回到第返回到第2步。步。计算步骤：计算步骤：计算步骤：计算步骤：第70页，共152页，编辑于2022年，星期三最短路问题最短路问题例例6.5 求下图求下图v1到到v7的最短路长及最短路线的最短路长及最短路线86252353421

42、0570862254411147510711v7已标号，计算结束。从已标号，计算结束。从v1到到v7的最短路长是的最短路长是 11,最短路线：最短路线：v1 v4 v6 v7P标号标号T标号标号12第71页，共152页，编辑于2022年，星期三最短路问题最短路问题从上例知，只要某点已标号，说明已找到起点从上例知，只要某点已标号，说明已找到起点vs到到该点的最短路线及最短距离，因此可以将每个点标该点的最短路线及最短距离，因此可以将每个点标号，求出号，求出vs到任意点的最短路线，如果某个点到任意点的最短路线，如果某个点vj不能不能标号，说明标号，说明vs不可达不可达vj。注：无向图最短路的求法只将

43、上述步骤注：无向图最短路的求法只将上述步骤2将弧改成边即可。将弧改成边即可。第72页，共152页，编辑于2022年，星期三最短路问题最短路问题例例6.6 求下图求下图v1到各点的最短距离及最短路线。到各点的最短距离及最短路线。4526178393261216180452231039612641166188122482418所有点都已标号，点上的标号就是所有点都已标号，点上的标号就是v1到该点的最短距离，最短路线就到该点的最短距离，最短路线就是红色的链。是红色的链。第73页，共152页，编辑于2022年，星期三最短路问题最短路问题课堂练习：课堂练习：1.用用Dijkstra算法求下图从算法求下图

44、从v1到到v6的最短距离及路线。的最短距离及路线。v3v54v1v2v4v635222421v1到到v6的最短路为：的最短路为：第74页，共152页，编辑于2022年，星期三最短路问题最短路问题2.求从求从v1到到v8的最短路径的最短路径237184566134105275934682第75页，共152页，编辑于2022年，星期三最短路问题最短路问题237184566134105275934682p2=2p4=1p1=0p6=3p7=3p5=6p3=8p8=10v1到到v8的最短路径为的最短路径为v1v4v7v5v8，最短距离为，最短距离为10第76页，共152页，编辑于2022年，星期三最短

45、路问题最短路问题3.求下图中求下图中v1点到另外任意一点的最短路径点到另外任意一点的最短路径v1v2v3v4v6v5322762133第77页，共152页，编辑于2022年，星期三最短路问题最短路问题v1V2V3V4 V6V5322762133024714第78页，共152页，编辑于2022年，星期三最短路问题最短路问题v1V2V3V4 V6V5322762133024714第79页，共152页，编辑于2022年，星期三最短路问题最短路问题算法适用条件：算法适用条件：Dijkstra算法只适用于全部权为非负情况，如果某算法只适用于全部权为非负情况，如果某边上权为负的，算法失效。边上权为负的，算

46、法失效。例例6.7 如右图所示中按如右图所示中按dijkstra算法算法可得可得P(v1)=5为从为从vsv1的最短路长的最短路长显然是错误的，从显然是错误的，从vsv2v1路长只路长只有有3。v2vsv15-58第80页，共152页，编辑于2022年，星期三最短路问题最短路问题最短路的矩阵算法最短路的矩阵算法FloyedFloyed算法算法最短路的矩阵算法是将图表示成矩阵形式，然后利用矩阵表，计算出最短路。矩阵算法的原理与标号算法完全相同，只是它采用了矩阵形式，更利于计算机计算。最短路的矩阵算法步骤如下：1.将图表示成矩阵形式。2.确定起点行，将其标号确定为0，将相应的列在矩阵表中划去。3.

47、在已标号的行中未划去的元素中找到最小元素aij，把它圈起来，此时把第j列划去，同时给第j行标号aij，并把第j行中未划去的各元素都加上aij。这里标号的含义同标号算法。第81页，共152页，编辑于2022年，星期三最短路问题最短路问题4.若还存在某些行未标号，则返回3。如果各行均已得到标号（或终点行获得标号），则终止计算。并倒向追踪，求得自起点到各点的最短通路。例6.8 用矩阵算法求下图中v1到v7的最短路。第82页，共152页，编辑于2022年，星期三最短路问题最短路问题解 先将图表示成矩阵形式，将第一行起点标号0，并划去第一列。0第83页，共152页，编辑于2022年，星期三最短路问题最短

48、路问题01第84页，共152页，编辑于2022年，星期三最短路问题最短路问题013第85页，共152页，编辑于2022年，星期三最短路问题最短路问题0134第86页，共152页，编辑于2022年，星期三最短路问题最短路问题01345第87页，共152页，编辑于2022年，星期三最短路问题最短路问题013457第88页，共152页，编辑于2022年，星期三最短路问题最短路问题下面再找出从v1到v7的最短通路。用逆推的方法，在终点v7所在的列中，圈起来的9在第五行，即知v7前面的点是v5，在找v5列，圈起来的7有两个，先随取一个，如第4行，则前面的点是v4，则找v4列，圈起来的是第二行，则v4前的

49、点是v2，再找v2列，圈起来的点在第一行，则前面的点是v1，即起点，个可以找到v1到v7的一条最短通路是：v1v2v4v5v7。第89页，共152页，编辑于2022年，星期三最短路问题最短路问题最短路问题的应用：最短路问题的应用：例例6.9 电信公司准备准备在甲、乙两地沿路架设一条光缆线，电信公司准备准备在甲、乙两地沿路架设一条光缆线，问如何架设使其光缆线路最短？下图给出了甲乙两地间的交问如何架设使其光缆线路最短？下图给出了甲乙两地间的交通图。权数表示两地间公路的长度（单位：公里）。通图。权数表示两地间公路的长度（单位：公里）。v1（甲地）（甲地）1517624431065v2v7(乙地乙地)

50、v3v4v5v6第90页，共152页，编辑于2022年，星期三最短路问题最短路问题解：这是一个求无向图的最短路的问题。解：这是一个求无向图的最短路的问题。第91页，共152页，编辑于2022年，星期三最短路问题最短路问题例例6.10 设备更新问题。某公司使用一台设备，在每年年初，设备更新问题。某公司使用一台设备，在每年年初，公司就要决定是购买新的设备还是继续使用旧设备。如果购公司就要决定是购买新的设备还是继续使用旧设备。如果购置新设备，就要支付一定的购置费，当然新设备的维修费用置新设备，就要支付一定的购置费，当然新设备的维修费用就低。如果继续使用旧设备，可以省去购置费，但维修费用就低。如果继续