第7章+图论-4(最短路问题)--离散数学-图论课件.ppt
《第7章+图论-4(最短路问题)--离散数学-图论课件.ppt》由会员分享,可在线阅读,更多相关《第7章+图论-4(最短路问题)--离散数学-图论课件.ppt(36页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、1返回 结束第七章图论引言引言7.1 图的基本概念图的基本概念7.2 7.3 图的矩阵表示图的矩阵表示7.4最短路径问题7.5 图的匹配图的匹配8.1 Euler图和图和Hamilton图图8.2 树树8.3 8.4 2返回 结束7.4最短路问题v一、问题的提出一、问题的提出 赋权图(网络):赋权图(网络):G=(V,E)中,给每条边中,给每条边 a=赋予一个非负实数权赋予一个非负实数权 wij,得到一个有向,得到一个有向网络网络3返回 结束7.4最短路问题v路径路径长度路径长度 非带权图的路径长度是指此路径上边的条数。非带权图的路径长度是指此路径上边的条数。带权图的路径长度是指路径上各边的权
2、之和带权图的路径长度是指路径上各边的权之和距离矩阵距离矩阵 对上述网络,定义对上述网络,定义 D=(dij)n n,n=|V|wij 当当 E dij=其它其它带权路径长度带权路径长度 对上述网络,路径对上述网络,路径 v1,v2,vk 的带权路径长度定义为的带权路径长度定义为4返回 结束7.4最短路问题最短路问题在实际工作中应用最短路问题在实际工作中应用1、通讯网络中最可靠问题、通讯网络中最可靠问题2、最大容量问题、最大容量问题3、统筹方法中求关键路线、统筹方法中求关键路线4、背包问题、背包问题5、选址问题、选址问题6、工件加工顺序问题、工件加工顺序问题7、中国邮递员问题、中国邮递员问题背包
3、问题背包问题(Knapsackproblem)是一种组合优化的NP完全问题。问题可以描述为:给定一组物品,每种物品都有自己的重量和价格,在限定的总重量内,我们如何选择,才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。5返回 结束6返回 结束7.4最短路问题vDijkstra算法vFloyd算法vFloyd-Warshall算法7返回 结束7.4最短路问题vDijkstra算法算法 Dijkstra算法是由荷兰计算机科学家算法是由荷兰计算机科学家狄克斯特拉狄克斯特拉(Dijkstra)于)于1959 年提出的,因此又叫狄克斯特拉算法。年提出的,因此又叫狄克斯特拉算
4、法。是从一个顶点到其余各顶点的最短路径算法,解决的是有向是从一个顶点到其余各顶点的最短路径算法,解决的是有向图中最短路径问题。图中最短路径问题。荷兰计算机科学教授荷兰计算机科学教授Edsger W.Dijkstra(1930-)在在1972年年获得美国计算机协会授予的图灵奖,这是计算机科学中最具获得美国计算机协会授予的图灵奖,这是计算机科学中最具声望的奖项之一。声望的奖项之一。Dijkstra算法是求出一个连通加权简单图中从结点算法是求出一个连通加权简单图中从结点a到结到结点点z的最短路。边的最短路。边(i,j)的权的权(i,j)0,且结点,且结点x的标号为的标号为L(x)。结束时,结束时,L
5、(z)是从是从a到到z的最短长度。的最短长度。举例来说,如果图中的顶点表示城市,而边上的举例来说,如果图中的顶点表示城市,而边上的权重权重表表示城市间开车行经的距离。示城市间开车行经的距离。Dijkstra算法可以用来找到两个算法可以用来找到两个城市之间的最短路径。城市之间的最短路径。8返回 结束7.4.1Dijkstra算法Dijkstra算法基本思想:把图中所有结点分为两组,每一个结点对应一个距离值。v第一组:包括已确定最短路径的结点,结点对应的距离值是由v0到此结点的最短路径长度;v第二组:包括尚未确定最短路径的结点,结点对应的距离值是v0经由第一组结点(中间结点)至此结点的最短路径长度
6、。按最短路径长度递增的顺序把第二组的结点加到第一组中去,直至v0可达的所有结点都包含于第一组。在这个过程中,总保持从v0到第一组各结点的最短路径长度都不大于从v0至第二组任何结点的路径长度。9返回 结束10返回 结束7.4.1Dijkstra算法procedure Dijkstra(G:所有权都为正数的加权连通简单图)G带有顶点av0,v1,vnz和权(vi,vj),若(vi,vj)不是G的边,则(vi,vj)fori:1tonL(vi)L(a):0S:(初始化标记,a的标记为0,其余结点标记为,S是空集whilezS beginu:不属于S的L(u)最小的一个顶点S:Su for所有不属于S
7、的顶点v if L(u)(u,v)L(v)thenL(v):L(u)(u,v)这样就给S中添加带最小标记的顶点并且更新不在S中的顶点的标记 endL(z)从a到z的最短长度dij11返回 结束7.4.1Dijkstra算法v下面给出该算法的框图:下面给出该算法的框图:通过框图,容易计算该算法计算量通过框图,容易计算该算法计算量 。12返回 结束13返回 结束7.4.1Dijkstra算法14返回 结束15返回 结束7.4.1Dijkstra算法vDijkstra算法算法(另外一种说明另外一种说明)求有向网络求有向网络 G=(V,A)中结点中结点v1 到其它结点的最短距离。到其它结点的最短距离。
8、设设D为为G的距离矩阵,的距离矩阵,n=|V|,向量,向量U=(u1,u2,un)的的ui 标记结点标记结点v1到到vi 的距离。的距离。S为已取得最短路的结点集合,其中每个结点在为已取得最短路的结点集合,其中每个结点在U中有中有固定标号标记取得的最短路的长度;固定标号标记取得的最短路的长度;S 为未取得最短路的为未取得最短路的结点集合,其中每个结点在结点集合,其中每个结点在U中有临时标号。中有临时标号。16返回 结束7.4.1Dijkstra算法0.初始化:初始化:u1(1)0,uj(1)d1j (j=2,3,n)S(1)v1,S(1)v2,v3,vn,m=1;1.选固定标号:在选固定标号:
9、在S(m)中求中求vk,使得,使得 uk(m)=minuj(m)|vj S(m)。若若 uk(m)=,则,则S(m)中的结点无最短路径;中的结点无最短路径;否则转否则转2。2.判结束:令判结束:令 S(m+1)S(m)vk,S(m+1)S(m)vk 若若 m=n 1,结束。,结束。3.修改临时标号:对所有修改临时标号:对所有vj S(m+1),令,令 uj(m+1)=minuj(m),uk(m)+dkj,m m+1;转;转1。17返回 结束18返回 结束7.4.1Dijkstra算法vDijkstra算法要求图上的权是非负数,否则结果不正确;vDijkstra算法同样适用于无向图,此时一个无向
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 图论 短路 问题 离散数学 课件
限制150内