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

《图与网络分析到最短路问题管理课件》由会员分享，可在线阅读，更多相关《图与网络分析到最短路问题管理课件（88页珍藏版）》请在金锄头文库上搜索。

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

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

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

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

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

6、下图所示的图所示的有向图有向图反映出来。反映出来。引例引例3 3v3v1v2v4v6v5图与网络分析到最短路问题管理课件图的基本概念与模型图的基本概念与模型点：点：研究对象（车站、国家、球队）；研究对象（车站、国家、球队）；点间连线：点间连线：对象之间的特定关系（陆地间有桥、铁对象之间的特定关系（陆地间有桥、铁路线、两球队比赛及结果路线、两球队比赛及结果) )。对称关系：对称关系：桥、道路、边界；用不带箭头的连线表桥、道路、边界；用不带箭头的连线表示，称为边。示，称为边。非对称关系：非对称关系：甲队胜乙队，用带箭头的连线表示，甲队胜乙队，用带箭头的连线表示，称为弧。称为弧。图：图：点及边（或弧

7、）组成。点及边（或弧）组成。注意：注意：一般情况下，图中的相对位置如何，点与点之间线一般情况下，图中的相对位置如何，点与点之间线的长短曲直，对于反映研究对象之间的关系，显的并不重的长短曲直，对于反映研究对象之间的关系，显的并不重要，因此，图论中的图与几何图，工程图等本质上不同。要，因此，图论中的图与几何图，工程图等本质上不同。图与网络分析到最短路问题管理课件对对称称关关系系非非对对称称关关系系无向图：无向图：图由点和边所构成的，图由点和边所构成的， 记作记作G = =V ,E(V V是点的集合，是点的集合，E E是边的集合是边的集合) 连接点连接点v vi i,v,vj jV V的边记作的边记

8、作e eijij=v vi i,v,vj j ，或者，或者 v vj j,v,vi i 。有向图：有向图：图是由点和弧所构成的，图是由点和弧所构成的， 记记作作D= V ,A (V V是是点点的的集集合合，A是是弧弧的的集集合合) ， 一条方向从一条方向从v vi i指向指向v vj j的弧，记作的弧，记作( (v vi i,v,vj j) )。 图的相关概念图的相关概念网络图：网络图：给图中的点和边赋予具体的含义和权数，如距离，给图中的点和边赋予具体的含义和权数，如距离，费用，容量等，记作费用，容量等，记作N.图与网络分析到最短路问题管理课件图的相关概念图的相关概念若边若边e eijij=v

9、 vi i, ,v vj jEE，称，称v vi i，v vj j是是e eij的的端点端点，也称，也称v vi i，v vj j是是相邻相邻的。称的。称e eijij是点是点v vi i（及点（及点v vj j）的）的关联边关联边。若两条边有一个公共的端点，则称这两条边若两条边有一个公共的端点，则称这两条边相邻相邻。v viv vjev vi，v vj相邻相邻 e与与v vi，v vj关联关联v vie1v vjv vke2点与边关联点与边关联点与点点与点相邻相邻边与边相邻边与边相邻图与网络分析到最短路问题管理课件若若某条边两个端点相同，称这条边为某条边两个端点相同，称这条边为环环。若两点之

10、间有多于一条的边，称这些边为若两点之间有多于一条的边，称这些边为多重边多重边。 无环、无多重边的无环、无多重边的图称为图称为简单图简单图。无环、但允许有多无环、但允许有多重边的图称为重边的图称为多重多重图图。v1e1e2e3v2v3e5e4v4v5注：注：无特别声明我们今后讨论的图都是简单图无特别声明我们今后讨论的图都是简单图图的相关概念图的相关概念图与网络分析到最短路问题管理课件图图G G中以点中以点v v为端点的边的数目，称为为端点的边的数目，称为v v在在G G中的中的次次( (度）度）， 记为记为d d（v v）。）。d(v1)=2 d(v2)=3 d(v3)=4 d(v4)=1 次为

11、次为1 1 的点为的点为悬挂点悬挂点，悬挂点的关联边称为，悬挂点的关联边称为悬悬挂边挂边，次为零的点称为，次为零的点称为孤立点孤立点。v1e1e2e3v2v3e5e4v4v5次为奇数的点称为次为奇数的点称为奇点奇点，否则称为，否则称为偶点偶点。图的相关概念图的相关概念图与网络分析到最短路问题管理课件给定图给定图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的一个的一个支撑

12、子图（部分图）支撑子图（部分图）。点全部保留点全部保留（a）（b）子图子图（c）部分图部分图子图与部分图（支撑子图）子图与部分图（支撑子图）图与网络分析到最短路问题管理课件图的连通性图的连通性链：链：设图设图G=G=（V V，E E）中有一个点、边交替序）中有一个点、边交替序列列 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中的

13、一中的一条链，而称点条链，而称点v v1 1,v,vn n为该链的两个端点。为该链的两个端点。对于简单图链也可以仅用点的序列来表示。对于简单图链也可以仅用点的序列来表示。如果一条链的如果一条链的两个端点是同一个点两个端点是同一个点，则称它为，则称它为闭链或圈闭链或圈；如果一条链的如果一条链的各边均不相同各边均不相同，则称此链为，则称此链为简单链简单链；更若一条链的更若一条链的各点、各边均不相同各点、各边均不相同，则称该链为，则称该链为初等链初等链。v1v3v5e1e2v7v8e7v2v4v6e3e4e5e6e8e9简单链简单链： 1=（v2，v1，v3，v6，v4，v3，v5）初等链初等链：

14、2=（v2，v1，v3，v5）图与网络分析到最短路问题管理课件图的连通性图的连通性最短链最短链: :网络中链上权值的和称为链的长度，网络中链上权值的和称为链的长度，以点以点v v1 1,v,vn n为端点的诸链中长度最短的链为端点的诸链中长度最短的链称为这两点的最短链。称为这两点的最短链。连通图：连通图：如果图如果图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 ，构造矩阵，构造矩阵称矩阵称矩阵A A为网络为网络N N的权矩阵。的权矩阵。图与网络分析到最短路问题管理课件v4v5v2v1v3234567894其其权矩阵权矩阵为为：注：注：当当G G为为无向图无向图时，时，权矩阵权矩阵为为对称对称矩阵。矩阵。图与网络分析到最短路问题管理课件图图G=G=（V V，E

16、E），），p p= =n n，构造矩阵，构造矩阵称矩阵称矩阵A A为为G G的邻接矩阵。的邻接矩阵。邻接矩阵邻接矩阵？vi与与vj不相邻不相邻图的矩阵表示图的矩阵表示图与网络分析到最短路问题管理课件其邻接矩阵为：其邻接矩阵为： v4v5v2v1v3注：注：当当G G为为无向图无向图时，时，邻接矩阵邻接矩阵为为对称对称矩阵。矩阵。图与网络分析到最短路问题管理课件 思考：思考：有甲、乙、丙、丁、戊、己六名运动员报名参加有甲、乙、丙、丁、戊、己六名运动员报名参加A A、B B、C C、D D、E E、F F六个项目的比赛，下表中打的是个运动员报名六个项目的比赛，下表中打的是个运动员报名参加比赛的项目

17、，问六个项目的比赛顺序应如何安排？做到每参加比赛的项目，问六个项目的比赛顺序应如何安排？做到每名运动员都不连续地参加两项比赛。名运动员都不连续地参加两项比赛。ABCDEF分析分析：点表示项目，边表示两个项目有同一名运动员参加：点表示项目，边表示两个项目有同一名运动员参加目的目的：在图中找出点序列，：在图中找出点序列，使得依次排列的两个点不使得依次排列的两个点不相邻，就找到了每名运动相邻，就找到了每名运动员不连续参加两项比赛的员不连续参加两项比赛的安排方案安排方案A、C、B、F、E、D ( (不唯一不唯一) )图与网络分析到最短路问题管理课件第八章第八章图与网络分析图与网络分析图的基本概念与模型

18、图的基本概念与模型树图和图的最小部分树树图和图的最小部分树最短路问题最短路问题网络最大流问题网络最大流问题最小费用最大流问题最小费用最大流问题 图与网络分析到最短路问题管理课件第八章第八章图与网络分析图与网络分析图的基本概念与模型图的基本概念与模型树图和图的最小部分树树图和图的最小部分树最短路问题最短路问题网络最大流问题网络最大流问题最小费用最大流问题最小费用最大流问题 图与网络分析到最短路问题管理课件7 7个村庄要在他们之间架设电话线，要求任何两个村庄都可个村庄要在他们之间架设电话线，要求任何两个村庄都可以互相通电话以互相通电话( (允许中转允许中转) )，并且，并且电话线根数最少电话线根数

19、最少？引例引例村庄村庄1村庄村庄4村庄村庄3村庄村庄6村庄村庄2村庄村庄5村庄村庄7分析分析：用七个点代表村庄，如果在某两个村庄之间架设电：用七个点代表村庄，如果在某两个村庄之间架设电话线，则相应的在两点之间连一条边，这样电话线网就可话线，则相应的在两点之间连一条边，这样电话线网就可以用一个图来表示，并且满足如下要求：以用一个图来表示，并且满足如下要求：连通图连通图图中有圈的话，从圈中任去掉一条边，余下的图仍连通图中有圈的话，从圈中任去掉一条边，余下的图仍连通为什么？为什么？图与网络分析到最短路问题管理课件树树村庄村庄1村庄村庄4村庄村庄3村庄村庄6村庄村庄2村庄村庄5村庄村庄7如果如果G=G

20、=（V V，E E）是一个无圈的连通图，则称）是一个无圈的连通图，则称G G为为树树。 树中必存在次为树中必存在次为1 1的点（悬挂点）的点（悬挂点）树中任两点必有一条链且仅有一条链；树中任两点必有一条链且仅有一条链；在树的两个不相邻的点之间添加一条边，就得到一个圈；在树的两个不相邻的点之间添加一条边，就得到一个圈； 反之，去掉树的任一条边，树就成为不连通图；反之，去掉树的任一条边，树就成为不连通图；n n个顶点的树有（个顶点的树有（n-1n-1）条边。）条边。树是无圈连通图中边数最多的，也是最脆弱的连通图！树是无圈连通图中边数最多的，也是最脆弱的连通图！图与网络分析到最短路问题管理课件145

21、241575237图的部分树（支撑树）图的部分树（支撑树）如果图如果图G=G=（V V，E E）的部分图）的部分图G=G=（V V，EE）是树，）是树， 则称则称GG是是G G的的部分树（或支撑树）部分树（或支撑树）。村庄村庄1村庄村庄4村庄村庄3村庄村庄6村庄村庄2村庄村庄5村庄村庄7部分树上各树枝上权值的和称为它的长度，其中长度部分树上各树枝上权值的和称为它的长度，其中长度最短的部分树，称其为该图的最短的部分树，称其为该图的最小部分树最小部分树（最小支撑（最小支撑树）。树）。点保留点保留边可去边可去仍是树仍是树不唯一不唯一思考：如何铺设电话线，使得思考：如何铺设电话线，使得电话线长度最少？

22、电话线长度最少？图与网络分析到最短路问题管理课件ijkml最小部分树的求法最小部分树的求法定理：定理：图中任一个点图中任一个点i，若，若j是与相邻点中距离最近的，是与相邻点中距离最近的， 则则边边 i,j 一定必含在该图的最小部分树内。一定必含在该图的最小部分树内。推论：推论：把图的所有点分成把图的所有点分成和和两个集合，则两集合之两个集合，则两集合之间连线的最短边一定包含在最小部分树内。间连线的最短边一定包含在最小部分树内。避圈法破圈法图与网络分析到最短路问题管理课件227541435175ABCDEST算法的步骤：算法的步骤： 1 1、在给定的赋权的连通图上任选一点、在给定的赋权的连通图上

23、任选一点vi,其余点在其余点在中中。 2 2、从、从 与与 的连线中找出权数最小的边的连线中找出权数最小的边 vi, vj ，这条边一定，这条边一定包含在最小部分树内，做以标记。包含在最小部分树内，做以标记。 3 3、令、令 vi ， ； 4 4、重复、重复2 2、3 3两步，直至所有点都包含在两步，直至所有点都包含在中为止。中为止。vi求解最小生成树的避圈算法求解最小生成树的避圈算法S图与网络分析到最短路问题管理课件77ABCDEST2254143515求解最小生成树的破圈算法求解最小生成树的破圈算法算法的步骤：算法的步骤： 1 1、在给定的赋权的连通图上任找一个圈。、在给定的赋权的连通图上

24、任找一个圈。 2 2、在所找的圈中去掉一个权数最大的边（如果有两条或两、在所找的圈中去掉一个权数最大的边（如果有两条或两条以上的边都是权数最大的边，则任意去掉其中一条）。条以上的边都是权数最大的边，则任意去掉其中一条）。 3 3、如果所余下的图已不包含圈，则计算结束，所余下的图、如果所余下的图已不包含圈，则计算结束，所余下的图即为最小生成树，否则返回第即为最小生成树，否则返回第1 1步。步。图与网络分析到最短路问题管理课件第八章第八章图与网络分析图与网络分析图的基本概念与模型图的基本概念与模型树图和图的最小部分树树图和图的最小部分树最短路问题最短路问题网络最大流问题网络最大流问题最小费用最大流

25、问题最小费用最大流问题 图与网络分析到最短路问题管理课件第八章第八章图与网络分析图与网络分析图的基本概念与模型图的基本概念与模型树图和图的最小部分树树图和图的最小部分树最短路问题最短路问题网络最大流问题网络最大流问题最小费用最大流问题最小费用最大流问题 图与网络分析到最短路问题管理课件什么是最短路问题？什么是最短路问题？固定起点的最短路固定起点的最短路Dijkstra( (狄克斯拉狄克斯拉) () (荷兰荷兰) )算法：标号法算法：标号法 逐次逼近算法逐次逼近算法(Ford(Ford(美国美国) )算法算法) )：修正标号法：修正标号法每每 对对 顶顶 点点 之之 间间 的的 最最 短短 路路

26、 路矩阵算法路矩阵算法(Floyd(Floyd(佛洛伊德佛洛伊德) )算法算法) )最短路问题最短路问题图与网络分析到最短路问题管理课件最短路问题提出最短路问题提出 在现实生活中，除公路运输网络、电讯网络在现实生活中，除公路运输网络、电讯网络等网络图以外，还有输油管线这样的图。在输油等网络图以外，还有输油管线这样的图。在输油管线图中，为反映油的输送情况，管线图中，为反映油的输送情况，两点间不仅有两点间不仅有连线，线上往往还标有箭头连线，线上往往还标有箭头，以表示油的流动方，以表示油的流动方向。又如，指挥系统图、控制系统图等图中都标向。又如，指挥系统图、控制系统图等图中都标有指向。从这样的一类图

27、中就可以概括为有指向。从这样的一类图中就可以概括为有向图有向图的概念。的概念。图与网络分析到最短路问题管理课件有向图有向图由点集由点集 和和V V 中元素的有序对的一个集合中元素的有序对的一个集合 所组成的二元组称为所组成的二元组称为有向图有向图，记为，记为D=D=（V V，A A）。）。 其中其中 V V中的元素中的元素 vi i叫做叫做顶点顶点， A A中元素中元素aijij叫做以叫做以vi i为始点（尾），为始点（尾），vj j为终点（首）为终点（首）的的弧弧。 aijij与与ajiji作为具有不同指向的弧是不同的。作为具有不同指向的弧是不同的。图与网络分析到最短路问题管理课件有向网络与

28、混合图有向网络与混合图如果在图如果在图D=D=（V V，A A）中，给）中，给每一弧赋予权值每一弧赋予权值，如，如 将弧将弧aijij=(=(vi i, ,vj j) )有权值有权值 wijij，记为，记为w( (aijij)=)=wijij则赋则赋权有向图权有向图D=D=（V V，A A）称为）称为有向网络有向网络，在不至于混，在不至于混淆时，也淆时，也简称网络简称网络。混合图如果一个图中既有边，也有弧，那么称这混合图如果一个图中既有边，也有弧，那么称这种图为混合图。它往往出现在既有单行线，又有种图为混合图。它往往出现在既有单行线，又有双行线的交通图中。双行线的交通图中。12534372图与

29、网络分析到最短路问题管理课件最短路问题引例最短路问题引例下图为下图为单行线单行线交通网，每弧旁的数字表示通过这条线交通网，每弧旁的数字表示通过这条线所需的费用。现在某人要从所需的费用。现在某人要从v1出发，通过这个交通网出发，通过这个交通网到到v8去，求使总费用最小的旅行路线。去，求使总费用最小的旅行路线。v2v523464v3v1v4v6121061210v8v9v72363图与网络分析到最短路问题管理课件从从v1到到v8：P1=（v1，v2，v5，v8）费用费用6+1+6=13P2=（v1，v3，v4， v6， v7，v8）费用费用 3+2+10+2+4=21P3=从从v1到到v8的旅行路

30、线的旅行路线 从从v1到到v8的路。的路。旅行路线总费用旅行路线总费用 路上所有弧权之和路上所有弧权之和。最短路问题中，最短路问题中，不考虑有向环、并行弧不考虑有向环、并行弧。v2v523464v3v1v4v6121061210v8v9v72363图与网络分析到最短路问题管理课件几个概念几个概念路：路：设设p p是是D D中一个首尾相连的弧的集合，如果中一个首尾相连的弧的集合，如果vs s是是它的第一条弧的始点，它的第一条弧的始点，vt t是它的最后一条弧的终是它的最后一条弧的终点，则称它是以点，则称它是以点点vs s为始点为始点，以，以点点vt t为终点为终点的一的一条路。条路。路长：路长：

31、路路p p中所有弧的权值的和称为路中所有弧的权值的和称为路p p的长，记为的长，记为设图设图D=D=（V V，A A）是一有向网络）是一有向网络 v2v523464v3v1V4v6121061210v8v9v72363图与网络分析到最短路问题管理课件设设P P是以点是以点vs s为始点，以点为始点，以点vt t为终点的所有路的集合，为终点的所有路的集合， 如果如果 , ,且且 ，则称，则称p p0 0是以点是以点vs s 为始点，以点为始点，以点vt t为终点的为终点的最短路最短路。而称其路长为。而称其路长为点点 vi i到点到点vj j的距离的距离，记为，记为 。几个概念几个概念注意：注意：

32、在有向网络中在有向网络中, ,一般一般最短路及一点到另一点的距离最短路及一点到另一点的距离最短路问题最短路问题是重要的最优化问题之一，可以直接应用于解是重要的最优化问题之一，可以直接应用于解决生产实际的许多问题决生产实际的许多问题:管道铺设、线路安排、厂区布局等。管道铺设、线路安排、厂区布局等。而且经常被作为一个基本工具来解决其他的优化问题。而且经常被作为一个基本工具来解决其他的优化问题。图与网络分析到最短路问题管理课件最短路问题求解方法最短路问题求解方法Dijkstra算法算法逐步逼近算法逐步逼近算法路矩阵算法路矩阵算法图与网络分析到最短路问题管理课件最短路问题求解方法最短路问题求解方法Di

33、jkstra算法算法逐步逼近算法逐步逼近算法路矩阵算法路矩阵算法图与网络分析到最短路问题管理课件求解最短路问题的求解最短路问题的Dijkstra算法算法条件条件：当所有：当所有wij 0时，时，用来用来求给定点求给定点vs到任一到任一个点个点vj 最短路最短路的公认的最好方法。的公认的最好方法。事实事实：如果：如果P是是D中从中从vs到到vj的最短路的最短路，vi是是P中的一中的一基解基解个点，那么，从个点，那么，从vs沿沿P到到vi的路是从的路是从vs到到vi的最的最基解基解短路。短路。 Dijkstra算法是算法是Dijkstra在在19591959年提出的，可用于求解年提出的，可用于求解

34、指定两点间的最短路问题指定两点间的最短路问题，或从指定点到其余各点的最短，或从指定点到其余各点的最短路问题。由于其以标号为主要特征，又称为路问题。由于其以标号为主要特征，又称为标号法标号法。v1v2v3v4v5最短路的子路是最短路最短路的子路是最短路图与网络分析到最短路问题管理课件Dijkstra算法基本思想算法基本思想 从始点从始点vs出发，逐步出发，逐步顺序地向外探寻顺序地向外探寻，每向外延伸每向外延伸一步一步都都要求是最短的要求是最短的。执行过程中，与每个点对应，记录下一个数执行过程中，与每个点对应，记录下一个数( (称为这个点的称为这个点的标号标号) ) 1.1.标号标号 P P（固定

35、标号或永久性标号）（固定标号或永久性标号）从始点从始点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到各点的最短路。

36、到各点的最短路。前点标号前点标号 j 表示始点表示始点vs到到vj的最短路上的最短路上vj的的前一点前一点。图与网络分析到最短路问题管理课件Dijkstra算法步骤算法步骤： 第二步：第二步：考虑满足条件考虑满足条件 的所有点；的所有点； vi具有具有P P 标号标号; ;vj j具有具有T T 标号标号; ; 修改修改vj的的T T标号为标号为 ，并将结果仍记为并将结果仍记为T T( (v vj j) )第第一一步步：始始点点标标上上固固定定标标号号 , ,其其余余各各点标临时性标号点标临时性标号 T T( (vj j)=)= , j, j 1; 1; 第三步：第三步：若网络图中已无若网络图

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

38、061210v8v9v72363v60,0M,M,v1,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去，使总费用最小的旅行路线去，使总费用最小的旅行路线图与网络分析到最短路问题管理课件v5v223464v3v1v4121061210v8v9

39、v72363v60,0M,v4,11v1,1M,M,M,v1,3图上标号法图上标号法v3,5v2,6v2,6永久标号永久标号临时标号临时标号v1出发到出发到v8去，使总费用最小的旅行路线去，使总费用最小的旅行路线图与网络分析到最短路问题管理课件v5v223464v3v1v4121061210v8v9v72363v60,0M,v4,11v1,1M,M,v1,3v5,12v5,9v5,9图上标号法图上标号法v3,5v2,6永久标号永久标号临时标号临时标号v5,10v1出发到出发到v8去，使总费用最小的旅行路线去，使总费用最小的旅行路线图与网络分析到最短路问题管理课件v5v223464v3v1v41

40、21061210v8v9v72363v60,0v5,10v1,1M,v5,12v1,3v5,9v5,12v3,5v2,6图上标号法图上标号法永久标号永久标号临时标号临时标号v5,10v1出发到出发到v8去，使总费用最小的旅行路线去，使总费用最小的旅行路线图与网络分析到最短路问题管理课件v5v223464v3v1v4121061210v8v9v72363v60,0v5,10v1,1M,v1,3v5,12v3,5v2,6图上标号法图上标号法v5,9永久标号永久标号临时标号临时标号标号结束标号结束反向追反向追踪踪v1出发到出发到v8去，使总费用最小的旅行路线去，使总费用最小的旅行路线图与网络分析到最

41、短路问题管理课件Dijkstra算法步骤算法步骤： 第二步：第二步：考虑满足条件考虑满足条件 的所有点；的所有点； vi具有具有P P 标号标号; ;vj j具有具有T T 标号标号; ; 修改修改vj的的T T标号为标号为 ，并将结果仍记为并将结果仍记为T T( (v vj j) )第第一一步步：始始点点标标上上固固定定标标号号 , ,其其余余各各点标临时性标号点标临时性标号 T T( (vj j)=)= , j, j 1; 1; 第三步：第三步：若网络图中已无若网络图中已无T T标号点，停止计算。标号点，停止计算。否则否则, , 令令 ，s s为为T T标号点集标号点集, , 然后然后将将

42、 的的T T 标号改成标号改成P P 标号标号 ，转入第二步。，转入第二步。图与网络分析到最短路问题管理课件例例 求如下交通网络中求如下交通网络中v1到到各点间最短路路长各点间最短路路长。DijkstraDijkstra算法（标号法）算法（标号法）算例算例31025v4v1v2v5v312262448混合图混合图图与网络分析到最短路问题管理课件无向网络无向网络: :负权弧时负权弧时。wijvivjwijwijvjvi无向网络中，最短路无向网络中，最短路最短链最短链。多个点对之间最短路？多个点对之间最短路？v1v2v312-3Dijkstra算法失效算法失效Dijkstra算法注意的问题算法注意

43、的问题逐步逼近算法逐步逼近算法路矩阵算法路矩阵算法图与网络分析到最短路问题管理课件5727461263202657710v3v1v2v4v5v6v7练习：求如下练习：求如下无向网络无向网络中中v v1 1到到v v7 7的最短的最短链链Dijkstra算法求最短链算法求最短链图与网络分析到最短路问题管理课件最短路问题求解方法最短路问题求解方法Dijkstra算法算法逐步逼近算法逐步逼近算法路矩阵算法路矩阵算法图与网络分析到最短路问题管理课件最短路问题求解方法最短路问题求解方法Dijkstra算法算法逐步逼近算法逐步逼近算法路矩阵算法路矩阵算法图与网络分析到最短路问题管理课件逐次逼近算法思想逐次

44、逼近算法思想 该公式表明，该公式表明，P(1)1j中的第中的第j个分量等于个分量等于P(0)1j的分量与基的分量与基本表本表(权矩阵权矩阵)中的第中的第j列相应元素路长的最小值，列相应元素路长的最小值，它相它相当于在当于在v1与与vj之间插入一个转接点之间插入一个转接点(v1,v2,vn中的任一中的任一个，含点个，含点v1与与vj)后所有可能路中的最短路的路长；每迭后所有可能路中的最短路的路长；每迭代一次，就相当与增加一个转接点，而代一次，就相当与增加一个转接点，而P(k)1j中的每一个中的每一个分量则随着分量则随着k的增加而呈不增的趋势！的增加而呈不增的趋势！v1v2v312-3图与网络分析

45、到最短路问题管理课件用于计算带有用于计算带有负权弧负权弧指定点指定点v1 1到其余各点到其余各点的最短路的最短路j=1,2,n. k=1,2,tn.2.2.计算计算逐次逼近算法基本步骤逐次逼近算法基本步骤 j=1,2,n.1.1.令令其元素即是其元素即是v1 1到到vj j的最短路长。的最短路长。3.3.当出现当出现时，时，v1v2v312-3图与网络分析到最短路问题管理课件例例 计算从计算从点点v1 1到所有其它顶点的最短路到所有其它顶点的最短路解：初始条件为解：初始条件为 以后按照公式以后按照公式 进行迭代。进行迭代。 直到得到直到得到 ，迭代停止。，迭代停止。v1v2v3v4v6v5v8

46、v72-35467-24-3342-1图与网络分析到最短路问题管理课件v1v2v3v4v5v6v7v8v8v7v6v5v4v3v2v1wijv1v2v3v4v6v5v8v72-35467-24-3342-1400-160240-33-3075-204200利用利用下标下标追踪追踪路径路径基本表基本表空格为无穷大空格为无穷大图与网络分析到最短路问题管理课件v1v2v3v4v5v6v7v8v8v7v6v5v4v3v2v1wijv1v2v3v4v6v5v8v72-35467-24-3342-1400-160240-33-3075-204200利用利用下标下标追踪追踪路径路径基本表基本表空格为无穷大空

47、格为无穷大图与网络分析到最短路问题管理课件最短路问题求解方法最短路问题求解方法Dijkstra算法算法逐步逼近算法逐步逼近算法路矩阵算法路矩阵算法图与网络分析到最短路问题管理课件最短路问题求解方法最短路问题求解方法Dijkstra算法算法逐步逼近算法逐步逼近算法路矩阵算法路矩阵算法图与网络分析到最短路问题管理课件 某些问题需要求网络上某些问题需要求网络上任意两点任意两点间的最间的最短路。当然，它也可以用标号算法依次改变短路。当然，它也可以用标号算法依次改变始点的办法来计算，但是比较麻烦。始点的办法来计算，但是比较麻烦。 这里介绍这里介绍FloydFloyd在在19621962年提出的年提出的路

48、矩阵法路矩阵法，它可直接求出网络中它可直接求出网络中任意两点间的最短路。任意两点间的最短路。FloydFloyd算法算法( (路矩阵法路矩阵法) )思想思想图与网络分析到最短路问题管理课件 考虑考虑D D中任意两点中任意两点vi i，vj j，如将，如将D D中中vi i，vj j以外的点都删掉，以外的点都删掉，得只剩得只剩vi i，vj j的一个子网络的一个子网络D D0 0，记，记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

49、 j的最短路记为的最短路记为 , ,则一定有则一定有vivjv1wijFloydFloyd算法算法( (路矩阵法路矩阵法) )思想思想 网络网络D=D=（V V，A A，W W），令），令U=(U=(d dijij) )n n n n， 表示表示D D中中vi i到到vj j的最的最短路的长度。短路的长度。dij图与网络分析到最短路问题管理课件 再在再在D D1 1中加入中加入v2 2及及D D中与中与vi，vj，v1， v2相关联的弧，得相关联的弧，得D D2 2，D D2 2中中vi到到vj的最短路长记为的最短路长记为 ，则有，则有FloydFloyd算法算法( (路矩阵法路矩阵法) )思

50、想思想图与网络分析到最短路问题管理课件FloydFloyd算法算法( (路矩阵法路矩阵法) )步骤步骤设有有向网络设有有向网络D=D=（V V，A A），其权矩阵为），其权矩阵为A=(A=(aijij) )n nn n，如下构造如下构造路矩阵序列路矩阵序列：则则n n阶路矩阵阶路矩阵D D( (n)n)中的元素中的元素d d(n)(n)ijij就是就是vi i到到vj j的最短路的路长。的最短路的路长。1.令权矩阵令权矩阵A A为初始路矩阵为初始路矩阵D D（0 0），），即令即令D D（0 0）=A=A2. 2. 依次计算依次计算K K阶路矩阵阶路矩阵D D（K K）= =（d(k)(k)i

51、jij）n nn n, k=1,2, k=1,2,n n，这里这里图与网络分析到最短路问题管理课件路矩阵序列的含义路矩阵序列的含义 K K阶路矩阵阶路矩阵D D（K K） 其中的元素表示相应两点间可能以点其中的元素表示相应两点间可能以点v1、v2、vk为为 转接点的所有路中路长最短的路的路长。转接点的所有路中路长最短的路的路长。D（0） 其其中的任一元素表示相应两点间无转接点时最短路路长。中的任一元素表示相应两点间无转接点时最短路路长。一阶路矩阵一阶路矩阵D D（1 1） 其中的其中的元素表示相应两点间可能以点元素表示相应两点间可能以点v v1 1为转接点的所有为转接点的所有路中路长最短的路的

52、路长；路中路长最短的路的路长；为使计算程序化，转接点按为使计算程序化，转接点按顶点下标的顺序顶点下标的顺序依次加入依次加入n n阶路矩阵阶路矩阵D D( (n)n) 其中的元素其中的元素d d(n)(n)ijij就是就是vi到到vj的可能以点的可能以点v1、v2、vn为为转接点的所有路中路长最短的路的路长。既是转接点的所有路中路长最短的路的路长。既是vi到到vj的最的最短路的路长。短路的路长。图与网络分析到最短路问题管理课件例例 求如下交通网络中求如下交通网络中各对点间最短路路长各对点间最短路路长。该图的权矩阵为该图的权矩阵为：FloydFloyd算法算法( (路矩阵法路矩阵法) )算例算例3

53、1025v4v1v2v5v312262448图与网络分析到最短路问题管理课件例例 求如下交通网络中求如下交通网络中各对点间最短路路长各对点间最短路路长。FloydFloyd算法算法( (路矩阵法路矩阵法) )算例算例31025v4v1v2v5v312262448图与网络分析到最短路问题管理课件利用公式利用公式发现发现第一行，第一列元素不变第一行，第一列元素不变31025v4v1v2v5v312262448图与网络分析到最短路问题管理课件利用公式利用公式发现发现第二行，第二列元素不变第二行，第二列元素不变31025v4v1v2v5v312262448图与网络分析到最短路问题管理课件利用公式利用公

54、式发现发现第三行，第三列元素不变第三行，第三列元素不变31025v4v1v2v5v312262448图与网络分析到最短路问题管理课件利用公式利用公式发现发现第四行，第四列元素不变第四行，第四列元素不变31025v4v1v2v5v312262448图与网络分析到最短路问题管理课件31025v4v1v2v5v312262448D(5)中的元素给出相应两点间中的元素给出相应两点间的最短路，其下标给出最短路的最短路，其下标给出最短路个顶点下标个顶点下标,比如：比如：6254图与网络分析到最短路问题管理课件已知有已知有7 7个村子，相互间道路的距离如下图示。拟合建一所个村子，相互间道路的距离如下图示。拟

55、合建一所小学，已知小学，已知A A处有小学生处有小学生3030人，人，B B处处4040人，人，C C处处2525人，人，D D处处2020人，人，E E处处5050人，人，F F处处6060人，人， G处处60人人,问小学应建在哪一个村子，问小学应建在哪一个村子，使学生上学最方便（使学生上学最方便（原则原则所有人走的总路程最短；所有人走的总路程最短；尽可尽可能公平。）。能公平。）。最短路问题算例最短路问题算例1(1(选址问题选址问题) )AGFECB522747163D26图与网络分析到最短路问题管理课件最短路问题算例最短路问题算例1(1(选址问题选址问题) )AGFECB522747163

56、D26图与网络分析到最短路问题管理课件最短路问题算例最短路问题算例1(1(选址问题选址问题) )图与网络分析到最短路问题管理课件图与网络分析到最短路问题管理课件图与网络分析到最短路问题管理课件图与网络分析到最短路问题管理课件图与网络分析到最短路问题管理课件图与网络分析到最短路问题管理课件图与网络分析到最短路问题管理课件A A处处3030人，人，B B处处4040人，人，C C处处2525人，人，D D处处2020人，人，E E处处5050人，人，F F处处6060人，人， G G处处6060人人. .02005014035036060015001754025024048060280012025

57、0240480210801500150120360210200125600601801801601004050024030032020012025024001700 1335 1430 1070 835 770770 1330A B C D E F GABCDEFG图与网络分析到最短路问题管理课件某工厂使用一台设备，每年年初工厂都要作出决定：如果继某工厂使用一台设备，每年年初工厂都要作出决定：如果继续使用旧的，要付维修费；如果买新的，要付购置费。试制续使用旧的，要付维修费；如果买新的，要付购置费。试制定一个五年更新计划，使工厂总支出最少？定一个五年更新计划，使工厂总支出最少？若该设备在各年的购

58、置费、不同役龄的残值及维修费如下表：若该设备在各年的购置费、不同役龄的残值及维修费如下表：项目项目购置费购置费设备役龄设备役龄维修费维修费残值残值第一年第一年 第二年第二年 第三年第三年第四年第四年 第五年第五年110- -154121- -263132- -382143- -4111154- -5180最短路问题算例最短路问题算例2(2(设备更新问题设备更新问题) )图与网络分析到最短路问题管理课件最短路问题算例最短路问题算例2(2(设备更新问题设备更新问题) )项目项目购置费购置费设备役龄设备役龄维修费维修费残值残值第一年第一年 第二年第二年 第三年第三年第四年第四年 第五年第五年110-

59、 -154120- -263132- -382143- -4111154- -5180弧弧（vi，vj）的权的权: 表示第表示第i年初购买的设备一直使用到第年初购买的设备一直使用到第j j年年年初所需支付的总费用，即第年初所需支付的总费用，即第i年初的购置费年初的购置费加上加上第一年、第二第一年、第二年、年、第（、第（j-i）年的维修费，再）年的维修费，再减去减去（j-i）年役龄残值。）年役龄残值。解：为将该问题化为最短路问题，用点解：为将该问题化为最短路问题，用点vi i表示第表示第i年初购年初购买一台新设备，并虚设点买一台新设备，并虚设点v6 6表示第五年年底。表示第五年年底。弧弧（vi，

60、vj）：表示第表示第i年初购买的设备一直使用到第年初购买的设备一直使用到第j年年年初（即第年初（即第j-1年年底）；年年底）；这样一来，这样一来，设备更新问题设备更新问题可归结为如下基本表中的求可归结为如下基本表中的求v1 1到到v6 6的最短路问题。的最短路问题。 用逐次逼近法较为简便用逐次逼近法较为简便图与网络分析到最短路问题管理课件项目项目购置费购置费设备役龄设备役龄维修费维修费残值残值第一年第一年 第二年第二年 第三年第三年第四年第四年 第五年第五年110- -154120- -263132- -382143- -4111154- -5180答：第一年初购买一台新设备一直用到第三年年初处理，答：第一年初购买一台新设备一直用到第三年年初处理，再购买一台新设备一直用到第五年底可使支付的总费用最再购买一台新设备一直用到第五年底可使支付的总费用最少。少。图与网络分析到最短路问题管理课件图与网络分析到最短路问题管理课件