最短路问题(课堂PPT)_第1页
最短路问题(课堂PPT)_第2页
最短路问题(课堂PPT)_第3页
最短路问题(课堂PPT)_第4页
最短路问题(课堂PPT)_第5页
已阅读5页,还剩19页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1、赋权图赋权图v给定赋权图的一个子图给定赋权图的一个子图H,定义,定义H的权为的权为H的所有边权的总和。的所有边权的总和。最短路问题最短路问题n对图对图G的每条边的每条边e,赋予一实数,赋予一实数(e),称为边,称为边e的权,可得一的权,可得一赋权图。赋权图。UDBVCEA712244731555v赋权图中一条路的权称为路长。赋权图中一条路的权称为路长。n在一个赋权图在一个赋权图G上,给定两个顶点上,给定两个顶点u和和 v,所谓,所谓u和和 v最短最短 路是指所有连接顶点路是指所有连接顶点u和和 v 的路中路长最短的路;的路中路长最短的路;nu和和 v最短路的路长也称为最短路的路长也称为u和和

2、v的距离。的距离。UDBVCEA227414731555vDijkstra算法的基本思想:算法的基本思想:),(),(),(00vuwuuduud,),(),(min),(00SvSuvuwuudSud(1)uvu0u1SPPSVSSu ,0设设S是是V的真子集,的真子集,vuuP0S如果是从如果是从u 0 到到 的最短路,的最短路,Su),(0uu),(0uu则则 ,并且,并且P的的 段是最短的段是最短的路,所以路,所以算法标号算法标号v令令l ij表示从顶点表示从顶点vi到顶点到顶点vj的距离;的距离; dij表示连接顶点表示连接顶点vi与顶点与顶点vj边上的权,即边上的权,即)(,)(,

3、GEvvGEvvwdjijiijij公式(公式(1)是)是Dijkstra算法的基础。算法的基础。算法以标号方式进行,每进行一次都增加一个标号点,算法以标号方式进行,每进行一次都增加一个标号点,直至找到所求的最短路。直至找到所求的最短路。,),(),(min),(00SvSuvuwuudSud(1)Dijkstra算法步骤算法步骤vStep0 在点在点vs上标号上标号lss=0;,minSvSvdlljiijsisk,kkvSSvSSnStep4 lst是所求的最短路长,反向追踪找出是所求的最短路长,反向追踪找出所求所求vs- vt最短路最短路.nStep3 令令SnStep2 令令S表示所有

4、已标号点,表示所有已标号点, 表示未标号点,表示未标号点, 计算计算lsj ,转,转Step3nStep1 若若vt已标号,转已标号,转Step4; 否则转否则转Step2;计算实例计算实例求连接求连接S、V的最短路的最短路SDBVCEA227414731555SDBVCEA22741473155502,s5,s4,s,s,s,s02,s2,sSDBVCEA22741473155502,s5,s4,s,s,s,s02,s2,s9,A4,A4,sSDBVCEA22741473155502,s5,s4,s,s,s,s02,s2,s9,A4,A4,s8,C4,ASDBVCEA227414731555

5、02,s5,s4,s,s,s,s02,s2,s9,A4,A4,s8,C4,A7,B7,BSDBVCEA22741473155502,s5,s4,s,s,s,s02,s2,s9,A4,A4,s8,C4,A7,B7,B8,E14,E8,ESDBVCEA22741473155502,s5,s4,s,s,s,s02,s2,s9,A4,A4,s8,C4,A7,B7,B8,E14,E8,E13,D13,DLUV = 13;S-V最短路为最短路为SABEDVSDBVCEA22741473155502,s5,s4,s,s,s,s02,s2,s9,A4,A4,s8,C4,A7,B7,B8,E14,E8,E13,

6、D13,D实例评述实例评述vDijkstra算法不仅找到了所求最短路,而且找到了从算法不仅找到了所求最短路,而且找到了从S点到其他所有顶点的最短路;这些最短路构成了图的点到其他所有顶点的最短路;这些最短路构成了图的一个连通无圈的支撑子图,即图的一个支撑树。一个连通无圈的支撑子图,即图的一个支撑树。SDBVCEA22741473155502,s5,s4,s,s,s,s02,s2,s9,A4,A4,s8,C4,A7,B7,B8,E14,E8,E13,D13,DvDijkstra算法也适用于有向赋权图算法也适用于有向赋权图.SDBVCEA712244731555选址问题选址问题v设设G表示一个矿区的

7、交通运输图,矿井和之间的里程是;表示一个矿区的交通运输图,矿井和之间的里程是;现在需建一个矿区煤炭运输站,把运输站设在哪个矿井所在地现在需建一个矿区煤炭运输站,把运输站设在哪个矿井所在地才能使得离运输站距离最远的矿井可运输里程最短。这就是最才能使得离运输站距离最远的矿井可运输里程最短。这就是最简单的选址问题。简单的选址问题。v矿区的交通运输图是一个赋权图,每个矿井是图的一个顶点。矿区的交通运输图是一个赋权图,每个矿井是图的一个顶点。v在赋权图在赋权图G中,定义顶点中,定义顶点u的离距为:的离距为:ivjvijc),(max)(uVvvudud中心问题中心问题网络网络G的一个中心是满足下列条件的

8、的一个中心是满足下列条件的G的顶点的顶点u选址问题可化为求选址问题可化为求G的中心问题。的中心问题。求图的中心的算法过程:求图的中心的算法过程:用用Dijkstra算法求出算法求出G的任意两点间的距离;的任意两点间的距离;求出每点的离距求出每点的离距d(v)求满足(求满足(2)的顶点)的顶点v即是中心即是中心),(min)(Vvvdud(2)实例实例图图7-15给出了一个矿区的交通运输图。应把运输站建给出了一个矿区的交通运输图。应把运输站建在哪个矿井才能满足选址要求?在哪个矿井才能满足选址要求?v3v4v5v2v6v1v763221.531.81.52.5v这个问题实际上只需求出这个问题实际上

9、只需求出G的一个中心即可。按上面的算的一个中心即可。按上面的算法过程,首先利用法过程,首先利用Dijkstra算法得到图算法得到图7-15的距离表;再的距离表;再求出每个点的离距,最后找出离距的最小者求出每个点的离距,最后找出离距的最小者v 6就是建运就是建运输站的矿井。输站的矿井。3 . 605 . 13 . 63 . 34368 . 45 . 108 . 48 . 15 . 25 . 15 . 43 . 63 . 38 . 13023 . 63 . 93 . 63 . 38 . 13023 . 33 . 6545 . 2520253 . 635 . 13 . 63 . 32033 . 96

10、5 . 43 . 93 . 6530)(76543217654321vvvvvvvvdvvvvvvvi4.8v*=注注:Dijkstra算法只适用于所有算法只适用于所有ij0的情形,当赋的情形,当赋权有向图中存在负权时,算法失效。如权有向图中存在负权时,算法失效。如v1v2v3 12-3用用Dijkstra算法可以得出从算法可以得出从1到到v2的最短路的权是的最短路的权是1,但实际,但实际上从上从1到到v2的最短路是(的最短路是(1, v3 ,v2),权是),权是-1。下面介绍具有负权赋权有向图下面介绍具有负权赋权有向图D的最短路的算法。的最短路的算法。不妨假设从任一点不妨假设从任一点vi到任

11、一点到任一点vj都有一条弧(如果在都有一条弧(如果在D中,中,( vi,vj ) A,则添加弧(,则添加弧( vi,vj )令)令wij=+ )。)。显然,从显然,从vs到任一点到任一点vj的最短路总是从的最短路总是从vs出发到某个点出发到某个点vi,再沿(再沿(vi,vj)到)到vj的,由前面的结论可知,从的,由前面的结论可知,从vs到到vi的的这条路必定是从这条路必定是从vs到到vi的最短路,所以的最短路,所以d(vs,vj)必满)必满足如下方程:足如下方程:ijisijswvvdvvd),(),(minijisijswvvdvvd),(),(min可用如下递推公式:为了求得这个方程的解),(,),(),(21nsssvvdvvdvvd),(令)(njwvvdsjjs21),(1), 2 , 1(),(),(321minnjwvvdvvdtijistijst)()(,对有,步时,对所有第若进行到某一步,例如njk21),(),(1jskjskvvdvvd)()(到各点的最短路的权。)既为,(则)(sjskvnjvvd21),(1v2v3v4v5v6v7v8v6-1-3-283-52-111-1217-3-5例:求例:求1到各点的最短路到各点的最

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论