图与网络分析到最短路问题管理课件.ppt

1、第第1页页第八章第八章图与网络分析图与网络分析 图的基本概念与模型图的基本概念与模型 树图和图的最小部分树树图和图的最小部分树 最短路问题最短路问题 网络最大流问题网络最大流问题 最小费用最大流问题最小费用最大流问题 第第2页页第八章第八章图与网络分析图与网络分析 图的基本概念与模型图的基本概念与模型 树图和图的最小部分树树图和图的最小部分树 最短路问题最短路问题 网络最大流问题网络最大流问题 最小费用最大流问题最小费用最大流问题 第第3页页 图论是应用非常广泛的运筹学分支，它已图论是应用非常广泛的运筹学分支，它已经广泛地应用于物理学控制论，信息论，工程经广泛地应用于物理学控制论，信息论，工程

2、技术，交通运输，经济管理，电子计算机等各技术，交通运输，经济管理，电子计算机等各项领域。对于科学研究，市场和社会生活中的项领域。对于科学研究，市场和社会生活中的许多问题，可以同图论的理论和方法来加以解许多问题，可以同图论的理论和方法来加以解决。例如，各种决。例如，各种通信线路的架设，输油管道的通信线路的架设，输油管道的铺设，铁路或者公路交通网络的合理布局铺设，铁路或者公路交通网络的合理布局等问等问题，都可以应用图论的方法，简便、快捷地加题，都可以应用图论的方法，简便、快捷地加以解决。以解决。引引 言言第第4页页 17361736年瑞士科学家欧拉发表了关于图论方面的第一年瑞士科学家欧拉发表了关于

3、图论方面的第一篇科学论文，解决了著名的哥尼斯堡七座桥问题。即一篇科学论文，解决了著名的哥尼斯堡七座桥问题。即一个漫步者如何能够走过这七座桥，并且每座桥只能走过个漫步者如何能够走过这七座桥，并且每座桥只能走过一次，最终回到原出发地。如图一次，最终回到原出发地。如图1 1所示。所示。引例引例1 1欧拉将这个问题抽象成欧拉将这个问题抽象成一笔画问一笔画问题题。即能否从某一点开始不重复。即能否从某一点开始不重复地一笔画出这个图形，最终回到地一笔画出这个图形，最终回到原点。原点。欧拉在他的论文中证明了欧拉在他的论文中证明了这是不可能的，这是不可能的，因为这个图形中因为这个图形中每一个顶点都与奇数条边相连

4、接，每一个顶点都与奇数条边相连接，不可能将它一笔画出，这就是古不可能将它一笔画出，这就是古典图论中的第一个著名问题。典图论中的第一个著名问题。第第5页页 在实际的生产和生活中，人们为了反映事物之间的在实际的生产和生活中，人们为了反映事物之间的关系，常常在纸上用点和线来画出各式各样的示意图。关系，常常在纸上用点和线来画出各式各样的示意图。引例引例2 2左图是我国北京、上海、重庆等左图是我国北京、上海、重庆等十四个城市之间的铁路交通图，十四个城市之间的铁路交通图，这里用这里用点表示城市，用点与点之点表示城市，用点与点之间的线表示城市之间的铁路线间的线表示城市之间的铁路线。诸如此类还有城市中的市政管

5、道诸如此类还有城市中的市政管道图，民用航空线图等等。图，民用航空线图等等。连云港连云港武汉武汉南京南京徐州徐州上海上海北京北京塘沽塘沽青岛青岛济南济南天津天津郑州郑州第第6页页 有六支球队进行足球比赛，我们分别用点有六支球队进行足球比赛，我们分别用点v1v6 6表示这六支球队，它们之间的比赛情况，也可以用表示这六支球队，它们之间的比赛情况，也可以用图反映出来，已知图反映出来，已知v1 1队战胜队战胜v2 2队队，v2 2队战胜队战胜v3 3队队，v3 3队战胜队战胜v5 5队队，如此等等。这个胜负情况，可以用下，如此等等。这个胜负情况，可以用下图所示的图所示的有向图有向图反映出来。反映出来。引

6、例引例3 3v3v1v2v4v6v5第第7页页图的基本概念与模型图的基本概念与模型点：点：研究对象（车站、国家、球队）；研究对象（车站、国家、球队）；点间连线：点间连线：对象之间的特定关系（陆地间有桥、铁对象之间的特定关系（陆地间有桥、铁路线、两球队比赛及结果路线、两球队比赛及结果)。对称关系：对称关系：桥、道路、边界；用不带箭头的连线表桥、道路、边界；用不带箭头的连线表示，称为边。示，称为边。非对称关系：非对称关系：甲队胜乙队，用带箭头的连线表示，甲队胜乙队，用带箭头的连线表示，称为弧。称为弧。图：图：点及边（或弧）组成。点及边（或弧）组成。注意：注意：一般情况下，图中的相对位置如何，点与点

7、之间线一般情况下，图中的相对位置如何，点与点之间线的长短曲直，对于反映研究对象之间的关系，显的并不重的长短曲直，对于反映研究对象之间的关系，显的并不重要，因此，图论中的图与几何图，工程图等本质上不同。要，因此，图论中的图与几何图，工程图等本质上不同。第第8页页对对称称关关系系非非对对称称关关系系无向图：无向图：图由点和边所构成的，图由点和边所构成的，记作记作G V,E(V V是点的集合，是点的集合，E E是边的集合是边的集合)连接点连接点v vi i,v,vj jV V的边记作的边记作e eijij=v vi i,v,vj j，或者，或者 v vj j,v,vi i。有向图：有向图：图是由点和

8、弧所构成的，图是由点和弧所构成的，记作记作D=V,A(V V是点的集合，是点的集合，A是弧的集合是弧的集合)，一条方向从一条方向从v vi i指向指向v vj j的的弧，记作弧，记作(v vi i,v,vj j)。图的相关概念图的相关概念网络图：网络图：给图中的点和边赋予具体的含义和权数，如距离，给图中的点和边赋予具体的含义和权数，如距离，费用，容量等，记作费用，容量等，记作N.第第9页页图的相关概念图的相关概念若边若边e eijij=v vi i,v vj jEE，称称v vi i，v vj j是是e eij的的端点端点，也称，也称v vi i，v vj j是是相邻相邻的。称的。称e eij

9、ij是点是点v vi i（及点（及点v vj j）的）的关联边关联边。若两条边有一个公共的端点，则称这两条边若两条边有一个公共的端点，则称这两条边相邻相邻。v viv vjev vi，v vj相邻相邻 e与与v vi，v vj关联关联v vie1v vjv vke2点与边关联点与边关联点与点点与点相邻相邻边与边相邻边与边相邻第第10页页若若某条边两个端点相同，称这条边为某条边两个端点相同，称这条边为环环。若两点之间有多于一条的边，称这些边为若两点之间有多于一条的边，称这些边为多重边多重边。无环、无多重边的无环、无多重边的图称为图称为简单图简单图。无环、但允许有多无环、但允许有多重边的图称为重边

10、的图称为多重多重图图。v1e1e2e3v2v3e5e4v4v5注：注：无特别声明我们今后讨论的图都是简单图无特别声明我们今后讨论的图都是简单图图的相关概念图的相关概念第第11页页图图G G中以点中以点v v为端点的边的数目，称为为端点的边的数目，称为v v在在G G中的中的次次(度）度），记为记为d d（v v）。）。d(v1)=2 d(v2)=3 d(v3)=4 d(v4)=1 次为次为1 1 的点为的点为悬挂点悬挂点，悬挂点的关联边称为，悬挂点的关联边称为悬悬挂边挂边，次为零的点称为，次为零的点称为孤立点孤立点。v1e1e2e3v2v3e5e4v4v5次为奇数的点称为次为奇数的点称为奇点奇

11、点，否则称为，否则称为偶点偶点。图的相关概念图的相关概念第第12页页给定图给定图G=G=（V V，E E），），若图若图G=G=（VV，EE），其中），其中VV V V，EE E E，则称，则称GG是是G G的的子图子图。给定图给定图G=G=（V V，E E），），若图若图G=G=（V V，EE），其中），其中EE E E，则称，则称GG是是G G的一个的一个支撑子图（部分图）支撑子图（部分图）。点点全部保留全部保留（a）（b）子图子图（c）部分图部分图子图与部分图（支撑子图）子图与部分图（支撑子图）第第13页页图的连通性图的连通性链：链：设图设图G=G=（V V，E E）中有一个点、边交替序

12、）中有一个点、边交替序列列 v v1 1,e,e1 1,v,v2 2,v vn-1n-1,e,en-1n-1,v vn n，若，若e ei i=(v vi i,v,vi+1i+1)，即这，即这(n-1n-1)条边把条边把n n个顶点串个顶点串连起来连起来，我们称这个交替序列为图，我们称这个交替序列为图G G中的中的一条链，而称点一条链，而称点v v1 1,v,vn n为该链的两个端点。为该链的两个端点。对于简单图链也可以仅用点的序列来表示。对于简单图链也可以仅用点的序列来表示。如果一条链的如果一条链的两个端点是同一个点两个端点是同一个点，则称它为，则称它为闭链或圈闭链或圈；如果一条链的如果一条

13、链的各边均不相同各边均不相同，则称此链为，则称此链为简单链简单链；更若一条链的更若一条链的各点、各边均不相同各点、各边均不相同，则称该链为，则称该链为初等链初等链。v1v3v5e1e2v7v8e7v2v4v6e3e4e5e6e8e9简单链简单链：1=（v2，v1，v3，v6，v4，v3，v5）初等链初等链：2=（v2，v1，v3，v5）第第14页页图的连通性图的连通性最短链最短链:网络中链上权值的和称为链的长度，网络中链上权值的和称为链的长度，以点以点v v1 1,v,vn n为端点的诸链中长度最短的链为端点的诸链中长度最短的链称为这两点的最短链。称为这两点的最短链。连通图：连通图：如果图如果

14、图G=G=（V V，E E）中的）中的任意任意两点都两点都是其某一条链的两个端点，则称图是其某一条链的两个端点，则称图G G是连是连通图，否则，称图通图，否则，称图G G是不连通的。是不连通的。v1v3v5e1e2v7v8e7v2v4v6e3e4e5e6e8e9为不连通图，为不连通图，有两个连通分有两个连通分图组成图组成第第15页页图的矩阵表示图的矩阵表示图的矩阵表示主要方法有：权矩阵、邻接矩阵。图的矩阵表示主要方法有：权矩阵、邻接矩阵。权矩阵权矩阵网络图网络图N=N=（V V，E E），），边边 v vi i，v vj j 的权为的权为w wijij ，构造矩阵构造矩阵 其其它它其其中中0E

15、v,va,)(aAjiijijijnnw称矩阵称矩阵A A为网络为网络N N的权矩阵。的权矩阵。v4v5v2v1v3234567894其其权矩阵权矩阵为为：12345v09247v90340v A 23085v44806v7056012345vvvvv注：注：当当G G为为无向图无向图时，时，权矩阵权矩阵为为对称对称矩阵。矩阵。第第17页页图图G=G=（V V，E E），），p p=n n，构造矩阵构造矩阵其它其中 0 Ev,v 1a ,)(aA jiijijnn称矩阵称矩阵A A为为G G的邻接矩阵。的邻接矩阵。邻接矩阵邻接矩阵？vi与与vj不相邻不相邻图的矩阵表示图的矩阵表示其邻接矩阵为：

16、其邻接矩阵为：0100000100100010110011010A v4v5v2v1v3注：注：当当G G为为无向图无向图时，时，邻接矩阵邻接矩阵为为对称对称矩阵。矩阵。思考：思考：有甲、乙、丙、丁、戊、己六名运动员报名参加有甲、乙、丙、丁、戊、己六名运动员报名参加A A、B B、C C、D D、E E、F F六个项目的比赛，下表中打的是个运动员报名六个项目的比赛，下表中打的是个运动员报名参加比赛的项目，问六个项目的比赛顺序应如何安排？做到每参加比赛的项目，问六个项目的比赛顺序应如何安排？做到每名运动员都不连续地参加两项比赛。名运动员都不连续地参加两项比赛。ABCDEF分析分析：点表示项目，边

17、表示两个项目有同一名运动员参加：点表示项目，边表示两个项目有同一名运动员参加目的目的：在图中找出点序列，：在图中找出点序列，使得依次排列的两个点不使得依次排列的两个点不相邻，就找到了每名运动相邻，就找到了每名运动员不连续参加两项比赛的员不连续参加两项比赛的安排方案安排方案A、C、B、F、E、D(不唯一不唯一)第第20页页第八章第八章图与网络分析图与网络分析 图的基本概念与模型图的基本概念与模型 树图和图的最小部分树树图和图的最小部分树 最短路问题最短路问题 网络最大流问题网络最大流问题 最小费用最大流问题最小费用最大流问题 第第21页页第八章第八章图与网络分析图与网络分析 图的基本概念与模型图

18、的基本概念与模型 树图和图的最小部分树树图和图的最小部分树 最短路问题最短路问题 网络最大流问题网络最大流问题 最小费用最大流问题最小费用最大流问题 第第22页页7 7个村庄要在他们之间架设电话线，要求任何两个村庄都可个村庄要在他们之间架设电话线，要求任何两个村庄都可以互相通电话以互相通电话(允许中转允许中转)，并且，并且电话线根数最少电话线根数最少？引例引例村庄村庄1村庄村庄4村庄村庄3村庄村庄6村庄村庄2村庄村庄5村庄村庄7分析分析：用七个点代表村庄，如果在某两个村庄之间架设电：用七个点代表村庄，如果在某两个村庄之间架设电话线，则相应的在两点之间连一条边，这样电话线网就可话线，则相应的在两

19、点之间连一条边，这样电话线网就可以用一个图来表示，并且满足如下要求：以用一个图来表示，并且满足如下要求：连通图连通图图中有圈的话，从圈中任去掉一条边，余下的图仍连通图中有圈的话，从圈中任去掉一条边，余下的图仍连通为什么？为什么？第第23页页树树村庄村庄1村庄村庄4村庄村庄3村庄村庄6村庄村庄2村庄村庄5村庄村庄7如果如果G=G=（V V，E E）是一个无圈的连通图，则称）是一个无圈的连通图，则称G G为为树树。树中必存在次为树中必存在次为1 1的点（悬挂点）的点（悬挂点）树中任两点必有一条链且仅有一条链；树中任两点必有一条链且仅有一条链；在树的两个不相邻的点之间添加一条边，就得到一个圈；在树的

20、两个不相邻的点之间添加一条边，就得到一个圈；反之，去掉树的任一条边，树就成为不连通图；反之，去掉树的任一条边，树就成为不连通图；n n个顶点的树有（个顶点的树有（n-1n-1）条边。）条边。树是无圈连通图中边数最多的，也是最脆弱的连通图！树是无圈连通图中边数最多的，也是最脆弱的连通图！第第24页页145241575237图的部分树（支撑树）图的部分树（支撑树）如果图如果图G=G=（V V，E E）的部分图）的部分图G=G=（V V，EE）是树，）是树，则称则称GG是是G G的的部分树（或支撑树）部分树（或支撑树）。村庄村庄1村庄村庄4村庄村庄3村庄村庄6村庄村庄2村庄村庄5村庄村庄7部分树上各

21、树枝上权值的和称为它的长度，其中长度部分树上各树枝上权值的和称为它的长度，其中长度最短的部分树，称其为该图的最短的部分树，称其为该图的最小部分树最小部分树（最小支撑（最小支撑树）。树）。点保留点保留边可去边可去仍是树仍是树不唯一不唯一思考：如何铺设电话线，使得思考：如何铺设电话线，使得电话线长度最少？电话线长度最少？第第25页页ijkml最小部分树的求法最小部分树的求法定理：定理：图中任一个点图中任一个点i，若，若j是与相邻点中距离最近的，是与相邻点中距离最近的，则边则边 i,j 一定必含在该图的最小部分树内。一定必含在该图的最小部分树内。推论：推论：把图的所有点分成把图的所有点分成和和两个集

22、合，则两集合之两个集合，则两集合之间连线的最短边一定包含在最小部分树内。间连线的最短边一定包含在最小部分树内。VVVV避圈法破圈法第第26页页227541435175ABCDESTVV 算法的步骤：算法的步骤：1 1、在给定的赋权的连通图上任选一点、在给定的赋权的连通图上任选一点vi,其余点在其余点在中中。2 2、从、从 与与 的连线中找出权数最小的边的连线中找出权数最小的边 vi,vj，这条边一定，这条边一定包含在最小部分树内，做以标记。包含在最小部分树内，做以标记。3 3、令、令 vi ，；4 4、重复、重复2 2、3 3两步，直至所有点都包含在两步，直至所有点都包含在中为止。中为止。VV

23、VVVVVviVV求解最小生成树的避圈算法求解最小生成树的避圈算法S第第27页页77ABCDEST2254143515求解最小生成树的破圈算法求解最小生成树的破圈算法 算法的步骤：算法的步骤：1 1、在给定的赋权的连通图上任找一个圈。、在给定的赋权的连通图上任找一个圈。2 2、在所找的圈中去掉一个权数最大的边（如果有两条或两、在所找的圈中去掉一个权数最大的边（如果有两条或两条以上的边都是权数最大的边，则任意去掉其中一条）。条以上的边都是权数最大的边，则任意去掉其中一条）。3 3、如果所余下的图已不包含圈，则计算结束，所余下的图、如果所余下的图已不包含圈，则计算结束，所余下的图即为最小生成树，否

24、则返回第即为最小生成树，否则返回第1 1步。步。第第28页页第八章第八章图与网络分析图与网络分析 图的基本概念与模型图的基本概念与模型 树图和图的最小部分树树图和图的最小部分树 最短路问题最短路问题 网络最大流问题网络最大流问题 最小费用最大流问题最小费用最大流问题 第第29页页第八章第八章图与网络分析图与网络分析 图的基本概念与模型图的基本概念与模型 树图和图的最小部分树树图和图的最小部分树 最短路问题最短路问题 网络最大流问题网络最大流问题 最小费用最大流问题最小费用最大流问题 第第30页页 固定起点的最短路固定起点的最短路Dijkstra(狄克斯拉狄克斯拉)()(荷兰荷兰)算法：标号法算

25、法：标号法 逐次逼近算法逐次逼近算法(Ford(Ford(美国美国)算法算法)：修正标号法：修正标号法 每每 对对 顶顶 点点 之之 间间 的的 最最 短短 路路 路矩阵算法路矩阵算法(Floyd(Floyd(佛洛伊德佛洛伊德)算法算法)最短路问题最短路问题第第31页页最短路问题提出最短路问题提出 在现实生活中，除公路运输网络、电讯网络在现实生活中，除公路运输网络、电讯网络等网络图以外，还有输油管线这样的图。在输油等网络图以外，还有输油管线这样的图。在输油管线图中，为反映油的输送情况，管线图中，为反映油的输送情况，两点间不仅有两点间不仅有连线，线上往往还标有箭头连线，线上往往还标有箭头，以表示

26、油的流动方，以表示油的流动方向。又如，指挥系统图、控制系统图等图中都标向。又如，指挥系统图、控制系统图等图中都标有指向。从这样的一类图中就可以概括为有指向。从这样的一类图中就可以概括为有向图有向图的概念。的概念。第第32页页有向图有向图由点集由点集 和和V V 中元素的有序对的一个集合中元素的有序对的一个集合 所组成的二元组称为所组成的二元组称为有向图有向图，记为，记为D=D=（V V，A A）。）。其中其中 V V中的元素中的元素 vi i叫做叫做顶点顶点，A A中元素中元素aijij叫做以叫做以vi i为始点（尾），为始点（尾），vj j为终点（首）为终点（首）的的弧弧。aijij与与aj

27、iji作为具有不同指向的弧是不同的。作为具有不同指向的弧是不同的。),(jiijvvaAivV 第第33页页有向网络与混合图有向网络与混合图 如果在图如果在图D=D=（V V，A A）中，给）中，给每一弧赋予权值每一弧赋予权值，如，如 将弧将弧aijij=(=(vi i,vj j)有权值有权值 wijij，记为，记为w(aijij)=)=wijij则赋则赋权有向图权有向图D=D=（V V，A A）称为）称为有向网络有向网络，在不至于混，在不至于混淆时，也淆时，也简称网络简称网络。混合图如果一个图中既有边，也有弧，那么称这混合图如果一个图中既有边，也有弧，那么称这种图为混合图。它往往出现在既有单

28、行线，又有种图为混合图。它往往出现在既有单行线，又有双行线的交通图中。双行线的交通图中。12534372第第34页页最短路问题引例最短路问题引例下图为下图为单行线单行线交通网，每弧旁的数字表示通过这条交通网，每弧旁的数字表示通过这条线所需的费用。现在某人要从线所需的费用。现在某人要从v1出发，通过这个交通出发，通过这个交通网到网到v8去，求使总费用最小的旅行路线。去，求使总费用最小的旅行路线。v2v523464v3v1v4v6121061210v8v9v72363从从v1到到v8：P1=（v1，v2，v5，v8）费用费用6+1+6=13P2=（v1，v3，v4，v6，v7，v8）费用费用 3+

29、2+10+2+4=21P3=从从v1到到v8的旅行路线的旅行路线 从从v1到到v8的路。的路。旅行路线总费用旅行路线总费用 路上所有弧权之和路上所有弧权之和。最短路问题中，最短路问题中，不考虑有向环、并行弧不考虑有向环、并行弧。v2v523464v3v1v4v6121061210v8v9v72363第第36页页几个概念几个概念路：路：设设p p是是D D中一个首尾相连的弧的集合，如果中一个首尾相连的弧的集合，如果vs s是是它的第一条弧的始点，它的第一条弧的始点，vt t是它的最后一条弧的终是它的最后一条弧的终点，则称它是以点，则称它是以点点vs s为始点为始点，以，以点点vt t为终点为终点

30、的一的一条路。条路。路长：路长：路路p p中所有弧的权值的和称为路中所有弧的权值的和称为路p p的长，记为的长，记为设图设图D=D=（V V，A A）是一有向网络）是一有向网络paijijawpw)()(v2v523464v3v1V4v6121061210v8v9v72363第第37页页设设P P是以点是以点vs s为始点，以点为始点，以点vt t为终点的所有路的集合，为终点的所有路的集合，如果如果 ,且且 ，则称，则称p p0 0是以点是以点vs s 为始点，以点为始点，以点vt t为终点的为终点的最短路最短路。而称其路长为。而称其路长为点点 vi i到点到点vj j的距离的距离，记为，记为

31、 。几个概念几个概念Pp 0)()(0pwMinpwPp)(),(0pwvvdts注意：注意：在有向网络中在有向网络中,一般一般),(),(sttsvvdvvd最短路及一点到另一点的距离最短路及一点到另一点的距离最短路问题最短路问题是重要的最优化问题之一，可以直接应用于解是重要的最优化问题之一，可以直接应用于解决生产实际的许多问题决生产实际的许多问题:管道铺设、线路安排、厂区布局等。管道铺设、线路安排、厂区布局等。而且经常被作为一个基本工具来解决其他的优化问题。而且经常被作为一个基本工具来解决其他的优化问题。第第38页页最短路问题求解方法最短路问题求解方法 Dijkstra算法算法 逐步逼近算

32、法逐步逼近算法 路矩阵算法路矩阵算法第第39页页最短路问题求解方法最短路问题求解方法 Dijkstra算法算法 逐步逼近算法逐步逼近算法 路矩阵算法路矩阵算法第第40页页求解最短路问题的求解最短路问题的Dijkstra算法算法条件条件：当所有：当所有wij 0时，时，用来用来求给定点求给定点vs到任一到任一个点个点vj 最短路最短路的公认的最好方法。的公认的最好方法。事实事实：如果：如果P是是D中从中从vs到到vj的最短路的最短路，vi是是P中的一中的一基解基解个点，那么，从个点，那么，从vs沿沿P到到vi的路是从的路是从vs到到vi的最的最基解基解短路。短路。Dijkstra算法是算法是Di

33、jkstra在在19591959年提出的，可用于求解年提出的，可用于求解指定两点间的最短路问题指定两点间的最短路问题，或从指定点到其余各点的最短，或从指定点到其余各点的最短路问题。由于其以标号为主要特征，又称为路问题。由于其以标号为主要特征，又称为标号法标号法。v1v2v3v4v5最短路的子路是最短路最短路的子路是最短路第第41页页Dijkstra算法基本思想算法基本思想 从始点从始点vs出发，逐步出发，逐步顺序地向外探寻顺序地向外探寻，每向外延伸每向外延伸一步一步都都要求是最短的要求是最短的执行过程中，与每个点对应，记录下一个数执行过程中，与每个点对应，记录下一个数(称为这个点的称为这个点的

34、标号标号)1.1.标号标号 P P（固定标号或永久性标号）固定标号或永久性标号）从始点从始点vs到该标号点到该标号点vj的最短路权的最短路权P(vj)。2.2.标号标号 T T（临时性标号）临时性标号）从始点从始点vs到该标号点到该标号点vj的最短路权的最短路权上界上界T(vj)。j,P(vj)j,T(vj)该方法的每一步就是去修改该方法的每一步就是去修改T T标号，并且把某一个具标号，并且把某一个具T T标号的点标号的点改变为具有改变为具有P标号的点，从而使标号的点，从而使D D中具中具P标号的顶点数多一个，标号的顶点数多一个，至多经过至多经过n-1步，就可以求出始点步，就可以求出始点vs到

35、各点的最短路。到各点的最短路。前点标号前点标号 j 表示始点表示始点vs到到vj的最短路上的最短路上vj的的前一点前一点。Dijkstra算法步骤算法步骤：第二步：第二步：考虑满足条件考虑满足条件 的所有点；的所有点；vi具有具有P P 标号标号;vj j具有具有T T 标号标号;修改修改vj的的T T标号为标号为 ，并将结果仍记为并将结果仍记为T T(v vj j)ijijjwvPvTvT)(),(min)(,)ijv vA第一步：第一步：始点标上固定标号始点标上固定标号 ,其余各其余各点标临时性标号点标临时性标号T T(vj j)=)=,j,j 1;1;()0sP v第三步：第三步：若网络

36、图中已无若网络图中已无T T标号点，停止计算。标号点，停止计算。否则否则,令令 ，s s为为T T标号点集标号点集,然后然后将将 的的T T 标号改成标号改成P P 标号标号 ，转入第二步。，转入第二步。0jv v1,6图上标号法图上标号法v5v223464v3v1v4121061210v8v9v72363v60,0M,M,v1,3M,M,M,v1,1v1,1永久标号永久标号永久标号永久标号临时标号临时标号v1出发到出发到v8去，使总费用最小的旅行路线去，使总费用最小的旅行路线v1,6图上标号法图上标号法v5v223464v3v1v4121061210v8v9v72363v60,0M,M,v1

37、,3M,M,M,0,0v1,1v4,11v1,3永久标号永久标号临时标号临时标号v1出发到出发到v8去，使总费用最小的旅行路线去，使总费用最小的旅行路线v5v223464v3v1v4121061210v8v9v72363v60,0M,v1,1M,M,M,1,3图上标号法图上标号法v4,11v1,3v1,6v3,5v3,5永久标号永久标号临时标号临时标号v1出发到出发到v8去，使总费用最小的旅行路线去，使总费用最小的旅行路线v5v223464v3v1v4121061210v8v9v72363v60,0M,v4,11v1,1M,M,M,v1,3图上标号法图上标号法v3,5v2,6v2,6永久标号永

38、久标号临时标号临时标号v1出发到出发到v8去，使总费用最小的旅行路线去，使总费用最小的旅行路线v5v223464v3v1v4121061210v8v9v72363v60,0M,v4,11v1,1M,M,v1,3v5,12v5,9v5,9图上标号法图上标号法v3,5v2,6永久标号永久标号临时标号临时标号v5,10v1出发到出发到v8去，使总费用最小的旅行路线去，使总费用最小的旅行路线v5v223464v3v1v4121061210v8v9v72363v60,0v5,10v1,1M,v5,12v1,3v5,9v5,12v3,5v2,6图上标号法图上标号法永久标号永久标号临时标号临时标号v5,10

39、v1出发到出发到v8去，使总费用最小的旅行路线去，使总费用最小的旅行路线v5v223464v3v1v4121061210v8v9v72363v60,0v5,10v1,1M,v1,3v5,12v3,5v2,6图上标号法图上标号法v5,9永久标号永久标号临时标号临时标号标号结束标号结束反向追踪反向追踪v1出发到出发到v8去，使总费用最小的旅行路线去，使总费用最小的旅行路线Dijkstra算法步骤算法步骤：第二步：第二步：考虑满足条件考虑满足条件 的所有点；的所有点；vi具有具有P P 标号标号;vj j具有具有T T 标号标号;修改修改vj的的T T标号为标号为 ，并将结果仍记为并将结果仍记为T

40、T(v vj j)ijijjwvPvTvT)(),(min)(,)ijv vA第一步：第一步：始点标上固定标号始点标上固定标号 ,其余各其余各点标临时性标号点标临时性标号T T(vj j)=)=,j,j 1;1;()0sP v第三步：第三步：若网络图中已无若网络图中已无T T标号点，停止计算。标号点，停止计算。否则否则,令令 ，s s为为T T标号点集标号点集,然后然后将将 的的T T 标号改成标号改成P P 标号标号 ，转入第二步。，转入第二步。0jv 第第51页页例例 求如下交通网络中求如下交通网络中v1到到各点间最短路路长各点间最短路路长。DijkstraDijkstra算例算例3102

41、5v4v1v2v5v312262448混合图混合图第第52页页 无向网络无向网络:负权弧时负权弧时。wijvivjwijwijvjvi无向网络中，最短路无向网络中，最短路最短链最短链。多个点对之间最短路？多个点对之间最短路？v1v2v312-3Dijkstra算法失效算法失效Dijkstra算法注意的问题算法注意的问题逐步逼近算法逐步逼近算法路矩阵算法路矩阵算法第第53页页5727461263202657710v3v1v2v4v5v6v7练习：求如下练习：求如下无向网络无向网络中中v v1 1到到v v7 7的最短的最短链链Dijkstra算法求最短链算法求最短链第第54页页最短路问题求解方法

42、最短路问题求解方法 Dijkstra算法算法 逐步逼近算法逐步逼近算法 路矩阵算法路矩阵算法第第55页页最短路问题求解方法最短路问题求解方法 Dijkstra算法算法 逐步逼近算法逐步逼近算法 路矩阵算法路矩阵算法第第56页页逐次逼近算法思想逐次逼近算法思想)1(11)(1ijkinikjwPMinP该公式表明，该公式表明，P(1)1j中的第中的第j个分量等于个分量等于P(0)1j的分量与基的分量与基本表本表(权矩阵权矩阵)中的第中的第j列相应元素路长的最小值，列相应元素路长的最小值，它相当它相当于在于在v1与与vj之间插入一个转接点之间插入一个转接点(v1,v2,vn中的任一个，中的任一个，

43、含点含点v1与与vj)后所有可能路中的最短路的路长；每迭代一后所有可能路中的最短路的路长；每迭代一次，就相当与增加一个转接点，而次，就相当与增加一个转接点，而P(k)1j中的每一个分量中的每一个分量则随着则随着k的增加而呈不增的趋势！的增加而呈不增的趋势！v1v2v312-3()(1)11kkjjPP(0)11jjPw第第57页页用于计算带有用于计算带有负权弧负权弧指定点指定点v1 1到其余各点到其余各点的最短路的最短路)1(11)(1ijkinikjwPMinPj=1,2,n.k=1,2,tn.2.2.计算计算逐次逼近算法基本步骤逐次逼近算法基本步骤(0)11jjPw j=1,2,n.1.1

44、.令令(k)(1)11kjjPP其元素即是其元素即是v1 1到到vj j的最短路长。的最短路长。3.3.当出现当出现时，时，v1v2v312-3例例 计算从计算从点点v1 1到所有其它顶点的最短路到所有其它顶点的最短路解：初始条件为解：初始条件为 0000111213140,2,5,3PPPP 以后按照公式以后按照公式 进行迭代。进行迭代。直到得到直到得到 ，迭代停止。，迭代停止。v1v2v3v4v6v5v8v72-35467-24-3342-1)1(11)(1ijkinikjwPMinP)1(1)(1tjtjPP(0)11jjPwv1v2v3v4v5v6v7v8v8v7v6v5v4v3v2v

45、1wij 01jP 11jP 21jP 31jP 41jP 51jPv1v2v3v4v6v5v8v72-35467-24-3342-1400-160240-33-3075-20420002530212303125613611021230312561236613681502123031236531236612366136871412368100212303123653123661236879123681002123031236612368791236810123653利用利用下标下标追踪追踪路径路径)1(11)(1ijkinikjwPMinP基本表基本表空格为无穷大空格为无穷大第第60页页v1v

46、2v3v4v5v6v7v8v8v7v6v5v4v3v2v1wij 01jP 11jP 21jP 31jP 41jP 51jPv1v2v3v4v6v5v8v72-35467-24-3342-1400-160240-33-3075-20420002530212303125613611021230312561236613681502123031236531236612366136871412368100212303123653123661236879123681002123031236612368791236810123653利用利用下标下标追踪追踪路径路径)1(11)(1ijkinikjwPMin

47、P基本表基本表空格为无穷大空格为无穷大第第61页页最短路问题求解方法最短路问题求解方法 Dijkstra算法算法 逐步逼近算法逐步逼近算法 路矩阵算法路矩阵算法第第62页页最短路问题求解方法最短路问题求解方法 Dijkstra算法算法 逐步逼近算法逐步逼近算法 路矩阵算法路矩阵算法第第63页页 某些问题需要求网络上某些问题需要求网络上任意两点任意两点间的最间的最短路。当然，它也可以用标号算法依次改变短路。当然，它也可以用标号算法依次改变始点的办法来计算，但是比较麻烦。始点的办法来计算，但是比较麻烦。这里介绍这里介绍FloydFloyd在在19621962年提出的年提出的路矩阵法路矩阵法，它可直

48、接求出网络中它可直接求出网络中任意两点间的最短路。任意两点间的最短路。FloydFloyd算法算法(路矩阵法路矩阵法)思想思想第第64页页 考虑考虑D D中任意两点中任意两点vi i，vj j，如将如将D D中中vi i，vj j以外的点都删掉，以外的点都删掉，得只剩得只剩vi i，vj j的一个子网络的一个子网络D D0 0，记记ij(0)ij ,A ijwv vd当否wijij为弧（为弧（vi i，vj）的权。的权。在在D D0 0中加入中加入v1 1及及D D中与中与vi i，vj j，v1 1相关联的弧，相关联的弧，得得D D1 1，D D1 1中中vi i到到vj j的最短路记为的最

49、短路记为 ,则一定有则一定有(1)ijd(1)(0)(0)(0)i11j min,ijijddddvivjv1wijFloydFloyd算法算法(路矩阵法路矩阵法)思想思想 网络网络D=D=（V V，A A，W W），令），令U=(U=(d dijij)n n n n，表示表示D D中中vi i到到vj j的最的最短路的长度。短路的长度。dij第第65页页 再在再在D D1 1中加入中加入v2 2及及D D中与中与vi，vj，v1，v2相关联的弧，得相关联的弧，得D D2 2，D D2 2中中vi到到vj的最短路长记为的最短路长记为 ，则有，则有(2)ijd(2)(1)(1)(1)iji22

50、j min,ijddddFloydFloyd算法算法(路矩阵法路矩阵法)思想思想(1)(0)(0)(0)i11j min,ijijdddd第第66页页FloydFloyd算法算法(路矩阵法路矩阵法)步骤步骤设有有向网络设有有向网络D=D=（V V，A A），其权矩阵为），其权矩阵为A=(A=(aijij)n nn n，AvvjiAvvwajijiijij),(,0),(,如下构造如下构造路矩阵序列路矩阵序列：则则n n阶路矩阵阶路矩阵D D(n n)中的元素中的元素d d(n)(n)ijij就是就是vi i到到vj j的最短路的路长。的最短路的路长。1.令权矩阵令权矩阵A A为初始路矩阵为初始