运筹学-图论.ppt

图论图论第五章 图与网络分析.主要内容：主要内容：1 1 图的基本概念与基本定理图的基本概念与基本定理2 2 树和最小支撑树树和最小支撑树3 3 最短路问题最短路问题4 4 最大流问题最大流问题5 5 最小费用流问题最小费用流问题.什么是图？什么是图？n图论图论中所谓的图是由一些中所谓的图是由一些点点(vertices)(vertices)，和一，和一些连接兩点的些连接兩点的边边(edges)(edges)所形成的所形成的.5.1 5.1 图的基本概念与基本定理图的基本概念与基本定理 图图论论是是应应用用非非常常广广泛泛的的运运筹筹学学分分支支，它它已已经经广广泛泛地地应应用用于于物物理理学学控控制制论论、信信息息论论、工工程程技技术术、交交通通运运输输、经经济济管管理理、电电子子计计算算机机等等各各项项领领域域。对对于于科科学学研研究究、市市场场和和社社会会生生活活中中的的许许多多问问题题，可可以以同同图图论论的的理理论论和和方方法法来来加加以以解解决决。例例如如：各各种种通通信信线线路路的的架架设设，输输油油管管道道的的铺铺设设，铁铁路路或或者者公公路路交交通通网网络络的的合合理理布布局局等等问问题题，都都可可以以应应用用图图论论的的方方法法，简简便、快捷地加以解决问题。便、快捷地加以解决问题。.关于图的第一篇论文是瑞士数学家关于图的第一篇论文是瑞士数学家欧拉欧拉（E.E.EulerEuler）在）在17361736年发表的解决年发表的解决“哥尼斯堡哥尼斯堡”七桥难七桥难题的论文。题的论文。德国的哥尼斯堡城有一条普雷格尔河，河中有德国的哥尼斯堡城有一条普雷格尔河，河中有两个岛屿，河的两岸和岛屿之间有七座桥相互连接，两个岛屿，河的两岸和岛屿之间有七座桥相互连接，当地的居民热衷于这样一个问题：一个散步者如何当地的居民热衷于这样一个问题：一个散步者如何能够走过这七座桥，并且每座桥只能走过一次，最能够走过这七座桥，并且每座桥只能走过一次，最终回到原出发地。尽管试验者很多，但是都没有成终回到原出发地。尽管试验者很多，但是都没有成功。为了寻找答案，功。为了寻找答案，17361736年欧拉将这个问题抽象成年欧拉将这个问题抽象成图所示图形的一笔画问题。图所示图形的一笔画问题。.Knigsberg(Koenigsberg)哥尼斯堡，原为东哥尼斯堡，原为东普鲁士普鲁士(Prussia)首首府，现属俄罗斯府，现属俄罗斯(飞飞地地)，名为加里宁格，名为加里宁格勒勒(Kaliningrad).n哥尼斯堡七桥问題哥尼斯堡七桥问題:要如何走过每座桥要如何走过每座桥恰一次，再返回出发点？恰一次，再返回出发点？普瑞格爾河.哥尼斯堡七桥问题哥尼斯堡七桥问题A AB BC CD D.哥尼斯堡七桥问题可简化为以下图形哥尼斯堡七桥问题可简化为以下图形哥尼斯堡七桥问题可简化为以下图形哥尼斯堡七桥问题可简化为以下图形其中的四个顶点都是奇顶点其中的四个顶点都是奇顶点其中的四个顶点都是奇顶点其中的四个顶点都是奇顶点A AB BC CD D.C CA AD DB B哥尼斯堡七橋問題哥尼斯堡七橋問題可以看成是：对这样一个封闭的可以看成是：对这样一个封闭的图形，是否可以一笔画完成它并且回到原点图形，是否可以一笔画完成它并且回到原点数学家欧数学家欧拉拉(Euler,1707-1783)(Euler,1707-1783)于于17361736年严格地证明了上述哥尼斯年严格地证明了上述哥尼斯堡七桥问题无解，并且由此开创了图论的典型思维方式及论证方式堡七桥问题无解，并且由此开创了图论的典型思维方式及论证方式.即能否从某一点开始不重复地一笔画出这个图形，即能否从某一点开始不重复地一笔画出这个图形，最终回到原点。欧拉在他的论文中证明了这是不可最终回到原点。欧拉在他的论文中证明了这是不可能的，因为这个图形中能的，因为这个图形中每一个顶点都与奇数条边相每一个顶点都与奇数条边相连接，不可能将它一笔画出连接，不可能将它一笔画出，这就是古典图论中的，这就是古典图论中的第一个著名问题。第一个著名问题。在实际的生产和生活中，人们为了反映事物在实际的生产和生活中，人们为了反映事物之间的关系，常常在纸上用之间的关系，常常在纸上用点和线点和线来画出各式各样来画出各式各样的示意图。的示意图。.图论应用举例图论应用举例n例如，在组织生产中，为完成某项任务，各工序之例如，在组织生产中，为完成某项任务，各工序之间怎样衔接，才能使生产任务完成得既快又好。间怎样衔接，才能使生产任务完成得既快又好。n一个邮递员送信，要走完他负责投递的全部街道，一个邮递员送信，要走完他负责投递的全部街道，完成任务后回到邮局，应该按照怎样的路线走，所完成任务后回到邮局，应该按照怎样的路线走，所走的路程最短。走的路程最短。n各种通信网络的合理架设各种通信网络的合理架设n交通网络的合理分布等交通网络的合理分布等.生生活活中中的的一一些些例例子子.台大网路架构图台大网路架构图.例例例例5.15.15.15.1 图图5.25.2是我国北京、上海、重庆等十四个城市之间的是我国北京、上海、重庆等十四个城市之间的铁路交通图，这里用点表示城市，用点与点之间的线表示城铁路交通图，这里用点表示城市，用点与点之间的线表示城市之间的铁路线。诸如此类还有城市中的市政管道图，民用市之间的铁路线。诸如此类还有城市中的市政管道图，民用航空线图等等。航空线图等等。石家庄石家庄太原太原北京北京天津天津塘沽塘沽济南济南青岛青岛徐州徐州连云港连云港南京南京上海上海郑州郑州武汉武汉重庆重庆图图5.35.3.例例例例5.25.25.25.2 有六支球队进行足球比赛，我们分别用有六支球队进行足球比赛，我们分别用点点v v1 1，v v6 6表示这六支球队，它们之间的比赛情表示这六支球队，它们之间的比赛情况，也可以用图反映出来，已知况，也可以用图反映出来，已知v v1 1队战胜队战胜v v2 2 队，队，v v2 2 队战胜队战胜v v3 3 队，队，v v3 3 队战胜队战胜v v5 5队，如此等等。这个胜负队，如此等等。这个胜负情况，可以用图情况，可以用图5.35.3所示的有向图反映出来所示的有向图反映出来v3v5v2v4v6v1.从从以以上上的的几几个个例例子子可可以以看看出出，我我们们用用点点和和点点之之间间的的线线所所构构成成的的图图，反反映映实实际际生生产产和和生生活活中中的的某某些些特特定定对对象象之之间间的的特特定定关关系系。通通常常用用点点表表示示研研究究对对象象，用用点点与与点点之之间间的的线线表表示示研研究究对对象象之之间间的的特特定定关关系系。由由于于在在一一般般情情况况下下，图图中中对对象象的的相相对对位位置置如如何何，点点与与点点之之间间线线的的长长短短曲曲直直，对对于于反反映映研研究究对对象象之之间间的的关关系系，显显的的并并不不重重要要，因因此此，图论中的图与几何图、工程图等本质上是不同的。图论中的图与几何图、工程图等本质上是不同的。.图图论论中中的的图图是是由由点点、点点与与点点之之间间的的线线所所组组成成的的。通通常常，我我们们把把点点与与点点之之间间不不带带箭箭头头的的线线叫叫做做边边，带带箭箭头头的的线线叫叫做做弧弧。如如果果一一个个图图是是由由点点和和边边所所构构成成的的，那那么么称称为为无无向向图图，记记作作G=(V，E)，其其中中V表表示示图图G 的的点点集集合合，E表表示示图图G的的边集合。连接点边集合。连接点vi,vjV 的边记作的边记作vi,vj，或者，或者vj,vi。如如果果一一个个图图是是由由点点和和弧弧所所构构成成的的，那那么么称称为为它它为为有有向向图图，记记作作D=(V,A)，其其中中V表表示示有有向向图图D的的点点集集合合，A表表示示有有向向图图D的的弧弧集集合合。一一条条方方向向从从vi 指指向向vj 的的弧弧，记记作作(vi,vj)。图的基本概念.图图5.4是一个无向图是一个无向图G=（V，E），），其中其中V=v1,v2,v3,v4 E=v1,v2,v2,v1,v2,v3,v3,v4,v1,v4,v2,v4,v3,v3v3v2v1v4图图 5.4 5.4.图图图图5.55.55.55.5 是一个有向图是一个有向图D=（V，A）其中其中V=v1,v2,v3,v4,v5,v6,v7 A=(v1,v2),(v1,v3),(v3,v2)(v3,v4),(v2,v4),(v4,v5),(v4,v6),(v5,v3),(v5,v4),(v5,v6),(v6,v7)图图 5.5v7v5v3v4v2v6v1.图的基本概念一一个个图图G或或有有向向图图D中中的的点点数数，记记作作P(G)或或P(D)，简简记记作作P；边边数数或或者者弧弧数数，记记作作q(G)或或者者q(D)，简记作，简记作q。如如果果边边vi ,vjE，那那么么称称vi,vj 是是边边的的端端点点，或或者者vi,vj是是相相邻邻的的。如如果果一一个个图图G中中，一一条条边边的的两两个个端端点点是是相相同同的的，那那么么称称为为这这条条边边是是环环，如如图图5.4中的边中的边v3,v3是环。是环。.图的基本概念 如如果果两两个个端端点点之之间间有有两两条条以以上上的的边边，那那么么称称为为它它们们为为多多重重边边，如如图图5.4中中的的边边v1,v2,v2,v1。v3v2v1v4.v1v5v4v3v2简单图简单图（2）（4）（3）（3）（2）多重图多重图v1v5v4v3v2（4）（6）（3）（3）（2）一个无环，无多重边的图称为一个无环，无多重边的图称为简单图，简单图，一个无环，有多重边的图称为一个无环，有多重边的图称为多重图多重图。.以以点点v为为端端点点的的边边的的个个数数称称为为点点v的的度度（次次），记记作作d(v),如如图图5.4中中d(v1)=3，d(v2)=4，d(v3)=4，d(v4)=3。度度为为零零的的点点称称为为弧弧立立点点，度度为为1的的点点称称为为悬悬挂挂点点。悬悬挂挂点点的的边边称称为为悬悬挂挂边边。度度为为奇奇数数的的点点称称为为奇奇点点，度为偶数的点称为度为偶数的点称为偶点偶点。端点的度端点的度 d(v)：点：点 v 作为端点的边的个数作为端点的边的个数 奇点：奇点：d(v)=奇数；奇数；.偶点：偶点：d(v)=偶数；偶数；悬挂点：悬挂点：d(v)=1；悬挂边：悬挂边：与悬挂点连接的边；与悬挂点连接的边；孤立点：孤立点：d(v)=0；空图：空图：E=，无边图无边图v1v2v3v4v5v6.v1v7v6v5v4v3v2V=v1,v2,v3,v4,v5,v6 ,v7 d(v1)=3;d(v2)=5;d(v3)=4;d(v4)=4;d(v5)=1;d(v6)=3;d(v7)=0其中其中 v5 为悬挂点，为悬挂点，v7 为孤立点。为孤立点。图图 5.7.定理定理5.1 所有顶点度数之和等于所有边数所有顶点度数之和等于所有边数的的2倍。倍。证明：证明：因为在计算各个点的度时，每条因为在计算各个点的度时，每条边被它的两个端点个用了一次。边被它的两个端点个用了一次。.定理定理定理定理5.25.2 在任一图中，奇点的个数必为偶数。在任一图中，奇点的个数必为偶数。证明：证明：证明：证明：设设 V1，V2 分别是图分别是图G中奇点和偶点的中奇点和偶点的 集合，由定理集合，由定理5.1，有，有因为因为 是偶数，是偶数，也是偶数，因此也是偶数，因此也必是偶数，从而也必是偶数，从而V1 中的点数是偶数。中的点数是偶数。.图的连通性：图的连通性：图的连通性：图的连通性：链：链：由两两相邻的点及其相关联的边构成的点边序列。由两两相邻的点及其相关联的边构成的点边序列。如如:v0 ,e1 ,v1 ,e2 ,v2，e3 ,v3 ,vn-1,en，vn;v0，vn分别分别为链的起点和终点为链的起点和终点。记作（。记作（v0 ,v1 ,v2，,v3 ,vn-1,vn）简单链：简单链：链中所含的边均不相同；链中所含的边均不相同；初等链：初等链：链中所含的点均不相同链中所含的点均不相同,也称通路；也称通路；圈：圈：若若 v0 vn 则称该链为开链，否则称为则称该链为开链，否则称为闭链或闭链或 回路或圈回路或圈；.简单圈：简单圈：如果在一个圈中所含的边均不相同如果在一个圈中所含的边均不相同初等初等圈：圈：除起点和终点外链中所含的点均不相除起点和终点外链中所含的点均不相 同的圈；同的圈；v1v2v4v3v5v6v7初等链初等链:(v1,v2,v3,v6,v7,v5)初等圈：初等圈：(v1,v2,v3,v5,v4,v1)简单链：简单链：(v1,v2,v3,v4 ,v5,v3)简单圈：简单圈：(v4,v1,v2,v3,v5,v7,v6,v3,v4).以后除特别声明，均指以后除特别声明，均指初等链和初等圈初等链和初等圈。v1v2v3v4v5不连通图不连通图v1v5v4v3v2v6连通图：连通图：图中任意两点之间均至少有一条通路，图中任意两点之间均至少有一条通路，否则称为不连通图。否则称为不连通图。连通图连通图.有向图：关联边有方向有向图：关联边有方向弧：弧：有向图的边有向图的边 a=(u,v),起点起点u,终点终点v；路：路：若有从若有从 u 到到 v 不考虑方向的链不考虑方向的链,且且 各方向一致各方向一致,则称之为从则称之为从u到到v 的路；的路；初等路初等路:各顶点都不相同的路；各顶点都不相同的路；初等回路初等回路:u=v 的初等路的初等路;连通图：连通图：若不考虑方向是若不考虑方向是 无向连通图无向连通图;强连通图：强连通图：任两点有路任两点有路;.基本概念点点边，弧边，弧无向图无向图链链端点端点关联边关联边有向图有向图圈圈始点，终点始点，终点 多重边多重边简单图简单图初等链初等链/圈圈度（次）度（次）环环多重图多重图简单链简单链/圈圈奇点，偶点奇点，偶点连通图连通图基础图基础图悬挂点悬挂点悬挂边悬挂边不连通图不连通图路路弧立点弧立点回路回路.例例 一摆渡人欲将一只狼、一头羊、一篮菜从河西渡一摆渡人欲将一只狼、一头羊、一篮菜从河西渡过河到河东，由于船小，一次只能带一物过河，并且狼与过河到河东，由于船小，一次只能带一物过河，并且狼与羊羊,羊与菜不能独处。给出渡河方法。羊与菜不能独处。给出渡河方法。解：用四维解：用四维0-10-1向量表示向量表示(人人,狼狼,羊羊,菜菜)在河西岸的状态在河西岸的状态(在河西岸则分量取在河西岸则分量取1,1,否则取否则取0)0)，共有，共有2 24 4=16=16 种状态，在种状态，在河东岸的状态类似记作。河东岸的状态类似记作。由题设由题设,状态状态(0,1,1,0),(0,0,1,1),(0,1,1,1)(0,1,1,0),(0,0,1,1),(0,1,1,1)是不允许的，是不允许的，从而对应状态从而对应状态(1,0,0,1),(1,1,0,0),(1,0,0,0)(1,0,0,1),(1,1,0,0),(1,0,0,0)也是不允许的。也是不允许的。以可允许的以可允许的1010个状态向量作为顶点，将可能互相转移个状态向量作为顶点，将可能互相转移的状态用线段连接起来构成一个图。的状态用线段连接起来构成一个图。根据此图便可找到渡河方法。根据此图便可找到渡河方法。.(1,1,1,1)(1,1,1,0)(1,1,0,1)(1,0,1,1)(1,0,1,0)(1,1,1,1)(1,1,1,0)(1,1,0,1)(1,0,1,1)(1,0,1,0)(0,0,0,0)(0,0,0,1)(0,0,1,0)(0,1,0,0)(0,1,0,1)(0,0,0,0)(0,0,0,1)(0,0,1,0)(0,1,0,0)(0,1,0,1)(0,1,0,1)(0,1,0,0)(0,0,1,0)(0,0,0,1)(0,0,0,0)(0,1,0,1)(0,1,0,0)(0,0,1,0)(0,0,0,1)(0,0,0,0)(1,0,1,0)(1,0,1,1)(1,1,0,1)(1,1,1,0)(1,1,1,1)(1,0,1,0)(1,0,1,1)(1,1,0,1)(1,1,1,0)(1,1,1,1)河西河西=(=(人人,狼狼,羊羊,菜菜)河东河东=(=(人人,狼狼,羊羊,菜菜)将将1010个顶点分别记为个顶点分别记为A A1 1,A A2 2,A A10 10,则渡河问题化为在该则渡河问题化为在该图中求一条从图中求一条从A A1 1到到A A1010的的路路.从图中易得到两条从图中易得到两条路路：A A1 1 A A6 6 A A3 3 A A7 7 A A2 2 A A8 8 A A5 5 A A1010;A A1 1 A A6 6 A A3 3 A A9 9 A A4 4 A A8 8 A A5 5 A A1010.图的矩阵表示1.邻接矩阵邻接矩阵 Adjacency matrixn表示图中两点之间的相互关系表示图中两点之间的相互关系n两点之间有弧或边的，用两点之间有弧或边的，用1表示，否则用表示，否则用0表表示，构成一个矩阵示，构成一个矩阵Av2v4v6v5v1v3v1v2v3v4v5v6v1011000v2101110v3110010v4010011v5011101v6000110.有向图有向图v1v7v2v5v3v4v6v8v9v1v2v3v4v5v6v7v8v9v1011100000v2000010000v3010100000v4000001000v5000101110v6000010100v7000000010v8000000000v9000010010.n矩阵矩阵A的元素全为的元素全为0的的行行所对应的点称为所对应的点称为汇汇点点 上图上图v8n矩阵矩阵A的元素全为的元素全为0的的列列所对应的点称为所对应的点称为源源点点 上图上图v1、v9.5.2 树和最小支撑树一、树及其性质一、树及其性质 在在各各种种各各样样的的图图中中，有有一一类类图图是是十十分分简简单单又又非非常具有应用价值的图，这就是常具有应用价值的图，这就是树。树。树。树。例例5.35.3 已已知知有有六六个个城城市市，它它们们之之间间要要架架设设电电话话线线，要要求求任任意意两两个个城城市市均均可可以以互互相相通通话话，并并且且电电话话线线的的总长度最短。总长度最短。.如如果果用用六六个个点点v1v6代代表表这这六六个个城城市市，在在任任意意两两个个城城市市之之间间架架设设电电话话线线，即即在在相相应应的的两两个个点点之之间间连连一一条条边边。这这样样，六六个个城城市市的的一一个个电电话话网网就就作作成成一一个个图图。表表示示任任意意两两个个城城市市之之间间均均可可以以通通话话，这这个个图图必必须须是是连连通通图图。并并且且，这这个个图图必必须须是是无无圈圈的的。否否则则，从从圈圈上上任任意意去去掉掉一一条条边边，剩剩下下的的图图仍仍然然是是六六个个城城市市的的一一个个电电话话网网。图图5.2.1是是一一个个不不含含圈圈的的连通图，代表了一个电话线网。连通图，代表了一个电话线网。.图图 5.2.1v6v3v4v2v5v1.树及其性质n树：树：既简单又很有用既简单又很有用n树：一个无圈的连通图树：一个无圈的连通图.组织结构图ManagerSubordSubord.荣国公荣国公贾代善贾代善贾赦贾赦贾政贾政贾琏贾琏贾珠贾珠贾宝玉贾宝玉 贾环贾环贾兰贾兰.定理定理n定理定理1：设：设G=(V,E)是一个树，是一个树，p(G)=2，则，则G中至少中至少 有两个悬挂点。有两个悬挂点。n定理定理2：图：图G=(V,E)是一个树的充要条件是是一个树的充要条件是G不含圈，不含圈，且恰有且恰有p-1条边。条边。n定理定理3：图：图G=(V,E)是一个树的充要条件是是一个树的充要条件是G是连通是连通 图，且图，且q(G)=p(G)-1。n定理定理4：图：图G=(V,E)是一个树的充要条件是任意两个是一个树的充要条件是任意两个 顶点之间恰有一条链。顶点之间恰有一条链。.推论推论n从一个树中去掉任意一条边，则余下的从一个树中去掉任意一条边，则余下的图是不连通的。图是不连通的。n在树中不相邻的两个点间添上一条边，在树中不相邻的两个点间添上一条边，则恰好得到一个圈则恰好得到一个圈.图的支撑树n设图设图T=(V,E)是图是图G=(V,E)的一个支撑子图，的一个支撑子图，如果如果T是一个树，则称是一个树，则称T是是G的一个的一个支撑树支撑树n定理定理5：图：图G有支撑树的充要条件是图有支撑树的充要条件是图G是连通是连通的。的。n破圈法：任取一个圈，破圈法：任取一个圈，从中去掉一条边，再从中去掉一条边，再 对余下的图重复直到对余下的图重复直到 不再含图时为止。不再含图时为止。.破圈法破圈法.避圈法避圈法n在图中任取一条边，找到一条与之不构在图中任取一条边，找到一条与之不构成圈的边，再找一条前两边不构成圈的成圈的边，再找一条前两边不构成圈的边边n重复直到不再能进行为止重复直到不再能进行为止n取出的边数为取出的边数为p-1条条.避圈法避圈法.最小支撑树问题最小支撑树问题n给定图给定图 G=(V,E)，对，对 G 中的每一条边中的每一条边 vi,vj，相应地有一个数，相应地有一个数 wij，则称这样的图为，则称这样的图为赋权图赋权图nwij 称为边称为边 vi,vj上的上的权权n权是与边有关的数量指标，可以是距离、时间、权是与边有关的数量指标，可以是距离、时间、费用等。费用等。.n赋权图不仅指出各个点之间的邻接关系，而且赋权图不仅指出各个点之间的邻接关系，而且同时也表示出各点之间的数量关系同时也表示出各点之间的数量关系n广泛应用于解决工程技术及管理等领域的最优广泛应用于解决工程技术及管理等领域的最优化问题化问题n最小支撑树问题就是赋权图上的最优化问题之最小支撑树问题就是赋权图上的最优化问题之一。一。.n设有一个连通图设有一个连通图G=(V,E)，每一边，每一边 e=vi,vj 有有一个非负权一个非负权 w(e)=wij (wij0)n如果如果T=(V,E)，是，是 G 的一个支撑树，称的一个支撑树，称E中所中所有边的权之和为支撑树有边的权之和为支撑树 T 的权，记为的权，记为 w(T).n如果支撑树如果支撑树 T*的权的权 w(T*)是是 G 的所有的所有支撑树的权中最小者，则称支撑树的权中最小者，则称T*是是 G 的最的最小支撑树小支撑树（最小树），即（最小树），即n式中对式中对 G 的所有支撑树的所有支撑树 T 取最小取最小.n最小支撑树问题就是要求最小支撑树问题就是要求G的最小支撑树。的最小支撑树。n方法有二：方法有二：n避圈法避圈法Kruskaln破圈法破圈法n常见求赋权图的最小树。常见求赋权图的最小树。.n 例5.4 某厂内联结六个车间的道路网如下所示，某厂内联结六个车间的道路网如下所示，已知每条路的长，要求沿道路架设联结六个车已知每条路的长，要求沿道路架设联结六个车间的电话线网，使电话线的总长最小。间的电话线网，使电话线的总长最小。v1v2v4v6v3v5657152344.避圈法求最小支撑树v1v2v4v6v3v515234ni=1,E0=。从。从E中选最小权边。依次选最中选最小权边。依次选最小权边，并使之不构成圈。共选小权边，并使之不构成圈。共选5条边条边v1v2v4v6v5657152344n最后，电话线总长最后，电话线总长1+2+3+4+5=15v3.破圈法求最小支撑树n任取一个圈，从中去掉一条权最大的边。任取一个圈，从中去掉一条权最大的边。依次重复，直到不含圈为止。依次重复，直到不含圈为止。v1v2v4v6v5657152344n最后，电话线总长最后，电话线总长1+2+3+4+5=15v3.矩阵计算方法T.TT.TTT.TTTT.TTTTT.TTTTTT.矩阵计算结果.一一.引言引言 最最短短路路径径问问题题是是图图论论中中十十分分重重要要的的最最优优化化问问题题之之一一，它它作作为为一一个个经经常常被被用用到到的的基基本本工工具具，可可以以解解决决生生产产实实际际中中的的许许多多问问题题，比比如如城城市市中中的的管管道道铺铺设设，线线路路安安排排，工工厂厂布布局局，设设备备更更新新等等。也可以用于解决其它的最优化问题。等等。也可以用于解决其它的最优化问题。5.3 最短路问题最短路问题.n例例5.6 如图所示的单行线交通网，每弧旁的数字如图所示的单行线交通网，每弧旁的数字表示这条单行线的距离。现在某人要从表示这条单行线的距离。现在某人要从 v1 出发，出发，通过这个交通网到达通过这个交通网到达 v8，求使总距离最短的旅行，求使总距离最短的旅行线路。线路。v1v7v2v5616321v32v4v610310v8v9246234?.n路很多路很多v1v7v2v5616321v32v4v610310v8v92462341+10+2+4=176+1+6=133+2+1+3+4=133+2+10+10+6=31哪一条最短？.最短路算法n如果如果P是是D中从中从 vs 到到 vi 的最短路，的最短路，vi 是是P中的中的一个点，那么从一个点，那么从 vs 沿沿P到到 vi 的路是从的路是从 vs 到到 vi 的最短路。的最短路。n1.图形的标号法图形的标号法n2.所有所有wij0的情形的情形Dijkstra法法1959.1.图形的标号法n先标出离终点最近的一段，然后标号与该点距离最短的点，先标出离终点最近的一段，然后标号与该点距离最短的点，继续逆推至始点。继续逆推至始点。C4AB1B2C1C2C3D1D2D3E1E2E3F1F2G5313668766688222255333333443510437597681310913121618从从A到到G的最短路为：的最短路为：A-B1-C2-D1-E2-F2-G.2.Dijkstra2.Dijkstra法法n基本思路：从基本思路：从vs出发，逐步地向外探寻最短路。出发，逐步地向外探寻最短路。n执行过程中，与每个点对应，记录下一个数执行过程中，与每个点对应，记录下一个数(称为称为此点的此点的标号标号)，n它或者表示从它或者表示从vs到该点的最短路的权到该点的最短路的权(称为称为P标号标号)n或者是从或者是从vs到该点的最短路的权的上界到该点的最短路的权的上界(称为称为T标标号号)n方法的每一步是修改方法的每一步是修改T标号，并且把某一个具标号，并且把某一个具T标标号的点改变为具号的点改变为具P标号的点，从而使标号的点，从而使D中具中具P标号的标号的点多一个，点多一个，n如此经过如此经过 p-1 步，就可以求出从步，就可以求出从vs到各点的最短路。到各点的最短路。.Dijkstra法具体步骤法具体步骤n开始开始(i=0)，令，令S0=vs,P(vs)=0,(vs)=0,对对每一个每一个v vs，令，令 T(v)=+,(v)=M,令令k=s1.如果如果Si=V，算法终止，这时，对每个，算法终止，这时，对每个v Si，d(vs,v)=P(v)；否则转入步骤；否则转入步骤22.考察每个使考察每个使(vk,vj)A且且vj Si的点的点vj。如果。如果T(v)P(vk)+wkj，则把，则把T(vj)修改为修改为P(vk)+wkj，把，把(vj)修改为修改为k；否则转入步骤；否则转入步骤3.3.令令T(vji)=min T(vj)n如果如果T(vji)P(vk)+wkj则T(v)=P(vk)+wkj(vj)修改为k找到minT(vj)，将其TP标号P(vj)=T(vj)，S=v1，6311111v4,v3,1143535v2,626v5,105951259v7,10v6,12v8v1到到v8最短路最短路 V13258.n求求s s到到t t的最短路。的最短路。s3t26745 2418 2 914 155 30 20 441611 619 6.s3t26745 24 18 2 9 14 15 5 30 20 44 16 11 6 19 6 0S=PQ=s,2,3,4,5,6,7,t.s3t26745 24 18 2 9 14 15 5 30 20 44 16 11 6 19 6 0S=PQ=s,2,3,4,5,6,7,t.s3t26745 24 18 2 9 14 15 5 30 20 44 16 11 6 19 6 15 9 14 0S=s PQ=2,3,4,5,6,7,t X XX.s3t26745 24 18 2 9 14 15 5 30 20 44 16 11 6 19 6 15 9 14 0S=s PQ=2,3,4,5,6,7,t X XX.s3t26745 24 18 2 9 14 15 5 30 20 44 16 11 6 19 6 15 9 14 0S=s,2 PQ=3,4,5,6,7,t X XX.s3t26745 24 18 2 9 14 15 5 30 20 44 16 11 6 19 6 15 9 14 0S=s,2 PQ=3,4,5,6,7,t X XXX 33.s3t26745 24 18 2 9 14 15 5 30 20 44 16 11 6 19 6 15 9 14 0S=s,2 PQ=3,4,5,6,7,t X XXX 33.s3t26745 24 18 2 9 14 15 5 30 20 44 16 11 6 19 6 15 9 14 0S=s,2,6 PQ=3,4,5,7,t X XXX 33 44XX 32.s3t26745 24 18 2 9 14 15 5 30 20 44 16 11 6 19 6 15 9 14 0S=s,2,6 PQ=3,4,5,7,t X XX 44X X 33X 32.s3t26745 18 2 9 14 15 5 30 20 44 16 11 6 19 6 15 9 14 0S=s,2,6,7 PQ=3,4,5,t X XX 44X 35X 59 X 24 X 33X 32.s3t26745 24 18 2 9 14 15 5 30 20 44 16 11 6 19 6 15 9 14 0S=s,2,6,7 PQ=3,4,5,t X XX 44X 35X 59 X X 33X 32.s3t26745 24 18 2 9 14 15 5 30 20 44 16 11 6 19 6 15 9 14 0S=s,2,3,6,7 PQ=4,5,t X XX 44X 35X 59 XX 51X 34 X 33X 32.s3t26745 18 2 9 14 15 5 30 20 44 16 11 6 19 6 15 9 14 0S=s,2,3,6,7 PQ=4,5,t X XX 44X 35X 59 XX 51X 34 X 33X 32 24.s3t26745 18 2 9 14 15 5 30 20 44 16 11 6 19 6 15 9 14 0S=s,2,3,5,6,7 PQ=4,t X XX 44X 35X 59 XX 51X 34 24X 50X 45 X 33X 32.s3t26745 18 2 9 14 15 5 30 20 44 16 11 6 19 6 15 9 14 0S=s,2,3,5,6,7 PQ=4,t X XX 44X 35X 59 XX 51X 34 24X 50X 45 X 33X 32.s3t26745 18 2 9 14 15 5 30 20 44 16 11 6 19 6 15 9 14 0S=s,2,3,4,5,6,7 PQ=t X XX 44X 35X 59 XX 51X 34 24X 50X 45 X 33X 32.s3t26745 18 2 9 14 15 5 30 20 44 16 11 6 19 6 15 9 14 0S=s,2,3,4,5,6,7 PQ=t X XX 44X 35X 59 XX 51X 34X 50X 45 X 33X 32 24.s3t26745 24 18 2 9 14 15 5 30 20 44 16 11 6 19 6 15 9 14 0S=s,2,3,4,5,6,7,t PQ=X XX 44X 35X 59 XX 51X 34X 50X 45 X 33X 32.s3t26745 24 18 2 9 14 15 5 30 20 44 16 11 6 19 6 15 9 14 0S=s,2,3,4,5,6,7,t PQ=X XX 44X 35X 59 XX 51X 34X 50X 45 X 33X 32.237184566134105275934682求从求从1到到8的最短路径的最短路径.237184566134105275934682X=1,w1=0min c12,c14,c16=min 0+2,0+1,0+3=min 2,1,3=1X=1,4,p4=1p4=1p1=0.237184566134105275934682X=1,4min c12,c16,c42,c47=min 0+2,0+3,1+10,1+2=min 2,3,11,3=2X=1,2,4,p2=2p1=0p4=1p2=2.237184566134105275934682X=1,2,4min c13,c23,c25,c47=min 0+3,2+6,2+5,1+2=min 3,8,7,3=3X=1,2,4,6,p6=3p2=2p4=1p1=0p6=3.237184566134105275934682X=1,2,4,6min c23,c25,c47,c67=min 2+6,2+5,1+2,3+4=min 8,7,3,7=3X=1,2,4,6,7,p7=3p2=2p4=1p1=0p6=3p7=3.237184566134105275934682X=1,2,4,6,7min 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,p5=6p2=2p4=1p1=0p6=3p7=3p5=6.237184566134105275934682X=1,2,4,6,7min 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,p3=8p2=2p4=1p1=0p6=3p7=3p5=6p3=8.237184566134105275934682X=1,2,3,4,6,7min c38,c58,c78=min 8+6,6+4,3+7=min 14,10,11=10X=1,2,3,4,5,6,7,8,p8=10p2=2p4=1p1=0p6=3p7=3p5=6p3=8p8=10.237184566134105275934682X=1,2,3,4,6,7,81到到8的最短路径为的最短路径为1，4，7，5，8，长度为，长度为10。p2=2p4=1p1=0p6=3p7=3p5=6p3=8p8=10.三、含有负权的最短路的求法三、含有负权的最短路的求法83-26-1-3-5-1-1212117-3-3v1v2v3v4v5v6v7v8例：例：求从求从v1 到到v8 的最短路的最短路.83-26-1-3-5-1-1212117-3-3v1v2v3v4v5v6v7v80-1-2383-26-1-3-5-1-1212117-3-3v1v2v3v4v5v6v7v80-5-2-71-15.83-26-1-3-5-1-1212117-3-3v1v2v3v4v5v6v7v80-5-2-7-3-1-56.83-26-1-3-5-1-1212117-3-3v1v2v3v4v5v6v7v80-5-2-7-3-1-56从从v1 到到 v8 的最短路的长度为：的最短路的长度为：6从从v1 到到 v8 的最短路线为：的最短路线为：v8v6v3v1.应用举例应用举例n设备更新问题。某企业使用一台设备，在每设备更新问题。某企业使用一台设备，在每年年初，企业领导部门就要决定是购置新的，年年初，企业领导部门就要决定是购置新的，还是继续使用旧的。若购置新设备，就要支还是继续使用旧的。若购置新设备，就要支付一定的购置费用；若继续使用旧的