图论最短路问题精品文稿.ppt

《图论最短路问题精品文稿.ppt》由会员分享，可在线阅读，更多相关《图论最短路问题精品文稿.ppt（36页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、图论最短路问题第1页，本讲稿共36页7.4最短路问题v一、问题的提出一、问题的提出 赋权图（网络）：赋权图（网络）：G=(V,E)中，给每条边中，给每条边 a=赋予一个非负实数权赋予一个非负实数权 wij，得到一个有向网络，得到一个有向网络第2页，本讲稿共36页7.4最短路问题v路径路径长度路径长度 非带权图的路径长度是指此路径上边的条数。非带权图的路径长度是指此路径上边的条数。带权图的路径长度是指路径上各边的权之和带权图的路径长度是指路径上各边的权之和距离矩阵距离矩阵 对上述网络，定义对上述网络，定义 D=(dij)n n，n=|V|wij 当当 E dij=其它其它带权路径长度带权路径长度

2、 对上述网络，路径对上述网络，路径 v1,v2,vk 的带的带权路径长度定义为权路径长度定义为第3页，本讲稿共36页7.4最短路问题最短路问题在实际工作中应用最短路问题在实际工作中应用1、通讯网络中最可靠问题、通讯网络中最可靠问题2、最大容量问题、最大容量问题3、统筹方法中求关键路线、统筹方法中求关键路线4、背包问题、背包问题5、选址问题、选址问题6、工件加工顺序问题、工件加工顺序问题7、中国邮递员问题、中国邮递员问题背包问题背包问题(Knapsackproblem)是一种组合优化的NP完全问题。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使

3、得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。第4页，本讲稿共36页7.4最短路问题v例一位旅客要从一位旅客要从A城到城到B城城1.他希望选择一条途中中转次数最少的路线；他希望选择一条途中中转次数最少的路线；2.他希望选择一条途中所花时间最短的路线；他希望选择一条途中所花时间最短的路线；3.他希望选择一条途中费用最小的路线；他希望选择一条途中费用最小的路线；v5v4v3v2v1v0 100 6030101020 5 50这些问题均是带权图上的最短路径问题。这些问题均是带权图上的最短路径问题。1.边上的权表示一站边上的权表示一站2.边上的权代表距离边上的权代表距离3.

4、边的权代表费用边的权代表费用 第5页，本讲稿共36页7.4最短路问题vDijkstra算法vFloyd算法vFloyd-Warshall算法第6页，本讲稿共36页7.4最短路问题vDijkstra算法算法 Dijkstra算法是由荷兰计算机科学家算法是由荷兰计算机科学家狄克斯特拉狄克斯特拉（Dijkstra）于于1959 年提出的，因此又叫狄克斯特拉算法。是从一个顶点到年提出的，因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法，解决的是有向图中最短路径问题。其余各顶点的最短路径算法，解决的是有向图中最短路径问题。荷兰计算机科学教授荷兰计算机科学教授Edsger W.Dijkstr

5、a(1930-)在在1972年获得年获得美国计算机协会授予的图灵奖，这是计算机科学中最具声望的奖项美国计算机协会授予的图灵奖，这是计算机科学中最具声望的奖项之一。之一。Dijkstra算法是求出一个连通加权简单图中从结点算法是求出一个连通加权简单图中从结点a到结点到结点z的最的最短路。边短路。边(i,j)的权的权(i,j)0，且结点，且结点x的标号为的标号为L(x)。结束时，。结束时，L(z)是从是从a到到z的最短长度。的最短长度。举例来说，如果图中的顶点表示城市，而边上的举例来说，如果图中的顶点表示城市，而边上的权重权重表示城市间表示城市间开车行经的距离。开车行经的距离。Dijkstra算法

6、可以用来找到两个城市之间的最短算法可以用来找到两个城市之间的最短路径。路径。第7页，本讲稿共36页7.4.1Dijkstra算法Dijkstra算法基本思想:把图中所有结点分为两组，每一个结点对应一个距离值。v第一组：包括已确定最短路径的结点，结点对应的距离值是由v0到此结点的最短路径长度；v第二组：包括尚未确定最短路径的结点，结点对应的距离值是v0经由第一组结点（中间结点）至此结点的最短路径长度。v按最短路径长度递增的顺序把第二组的结点加到第一组中去，直至v0可达的所有结点都包含于第一组。在这个过程中，总保持从v0到第一组各结点的最短路径长度都不大于从v0至第二组任何结点的路径长度。第8页，

7、本讲稿共36页7.4.1Dijkstra算法设源点为v0v初始时v0进入第一组，v0的距离值为0；第二组包含其它所有结点，这些结点对应的距离值这样确定（设vi为第二组中的结点）v然后每次从第二组的结点中选一个其距离值为最小的结点vm加到第一组中。每往第一组加入一个结点vm，就要对第二组的各结点的距离值作一次修正（设vi为第二组的结点）：v若加进vm做中间结点使得v0至vi的路径长度更短（即vi的距离值vm的距离值+Wmi），则要修改vi的距离（vi的距离值vm的距离值+Wmi）。修改后再选距离值最小的一个结点加入到第一组中，。如此进行下去，直至第一组囊括图的所有结点或再无可加入第一组的结点存在

8、。显然，这种从第二组的结点中选距离值最小的结点扩展是一种贪心策略。第9页，本讲稿共36页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的顶点v if L(u)(u,v)L(v)thenL(v):L(u)(u,v)这样就给S中添加带最小标记的顶点并且更新不在S中的

9、顶点的标记 endL(z)从a到z的最短长度dij第10页，本讲稿共36页7.4.1Dijkstra算法v下面给出该算法的框图：下面给出该算法的框图：通过框图，容易计算该算法计算量通过框图，容易计算该算法计算量 。第11页，本讲稿共36页7.4.1Dijkstra算法下面通过一个实例来说明Dijkstra算法是如何工作的。第12页，本讲稿共36页7.4.1Dijkstra算法第13页，本讲稿共36页7.4.1Dijkstra算法v0次迭代L(a)0L(b)L(c)L(d)L(e)L(z)S1次迭代ua，SaL(a)(a,b)044L(b)L(a)(a,c)022L(c)L(a)(a,d)0L(

10、a)(a,e)0L(a)(a,z)0L(b)4，L(c)2，L(d)L(e)L(z)2次迭代uc，Sa,cL(c)(c,b)213L(b)L(c)(c,d)2810L(d)L(c)(c,e)21012L(e)L(c)(c,z)2L(b)3，L(d)10，L(e)12，L(z)3次迭代ub，Sa,c,bL(b)(b,d)358L(d)L(b)(b,e)3145623108abcdez用Dijkstra算法求a和z之间最短路所用的步骤。L(b)(b,z)3L(d)8，L(e)12，L(z)4次迭代ud，Sa,c,b,dL(d)(d,e)8210L(e)L(d)(d,z)8614L(z)L(e)10

11、，L(z)145次迭代ue，Sa,c,b,d,eL(e)(e,z)10313L(z)L(z)13结 束uz，Sa,c,b,d,e,z从a到z的最短路的长度为13。第14页，本讲稿共36页7.4.1Dijkstra算法vDijkstra算法算法(另外一种说明另外一种说明)求有向网络求有向网络 G=(V,A)中结点中结点v1 到其它结点的最短距离。到其它结点的最短距离。设设D为为G的距离矩阵，的距离矩阵，n=|V|，向量，向量U=(u1,u2,un)的的ui 标记标记结点结点v1到到vi 的距离。的距离。S为已取得最短路的结点集合，其中每个结点在为已取得最短路的结点集合，其中每个结点在U中有固定标

12、号中有固定标号标记取得的最短路的长度；标记取得的最短路的长度；S 为未取得最短路的结点集合，其为未取得最短路的结点集合，其中每个结点在中每个结点在U中有临时标号。中有临时标号。第15页，本讲稿共36页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.选固定标号：在选固定标号：在S(m)中求中求vk，使得，使得 uk(m)=minuj(m)|vj S(m)。若若 uk(m)=，则，则S(m)中的结点无最短路径；否则转中的结点无最短路径；否则转2。2.判结束：令判结束：令 S(m+1)S(m)vk

13、,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。第16页，本讲稿共36页7.4.1Dijkstra算法vDijkstra算法只求出图中一个特定的顶点到其他各定点的最短路。但在许多实际问题中，需求出任意两点之间的最短路，如全国各城市之间最短的航线，选址问题等。当然，要求出一个图的任意两点间的最短距路，只需将图中每一个顶点依次视为始点，然后用Dijkstra算法就可以了。vDijkstra算法在物流配送中的应用vOSPF（openshort

14、estpathfirst,开放最短路径优先）算法是Dijkstra算法在网络路由中的一个具体实现。第17页，本讲稿共36页7.4.1Dijkstra算法vDijkstra算法要求图上的权是非负数，否则结果不正确；vDijkstra算法同样适用于无向图，此时一个无向边次相当于两个有向边。v利用求最短路的方法求最长路。由于存在负权（求最长路和负权等价），所以在这里Dijkstra算法不适用了，必须采用Floyd算法-动态规划算法vFloyd算法的功能是通过一个图的权值矩阵求出它的每两点间的最短路径矩阵.第18页，本讲稿共36页7.4.2Floyd算法v如果有一个矩阵D=d(ij)，其中d(ij)0

15、表示i城市到j城市的距离。若i与j之间无路可通，那么d(ij)就是无穷大。又有d(ii)=0。通过这个距离矩阵D，把任意两个城市之间的最短路径找出来。v【分析】对于任何一个城市而言，i到j的最短距离不外乎存在经过i与j之间的k和不经过k两种可能，所以可以令k=1，2，3，.，n(n是城市的数目)，检查d(ij)与d(ik)+d(kj)的值；d(ik)与d(kj)分别是目前为止所知道的i到k与k到j的最短距离，因此d(ik)+d(kj)就是i到j经过k的最短距离。所以，若有d(ij)d(ik)+d(kj)，就表示从i出发经过k再到j的距离要比原来的i到j距离短，自然把i到j的d(ij)重写为d(

16、ik)+d(kj)，每当一个k查完了，d(ij)就是目前的i到j的最短距离。重复这一过程，最后当查完所有的k时，d(ij)里面存放的就是i到j之间的最短距离了。第19页，本讲稿共36页7.4.2Floyd算法定义定义7.4.1:已知矩阵A(aij)ml，B(bjk)ln，规定CA*B(cij)mn，其中cijmin(ai1b1j,ai2b2j,ailblj)定义定义7.4.2已知矩阵A(aij)mn，B(bij)mn，规定DAB(dij)mn，其中dijmin(aij,bij)可以利用上面定义的运算求任意两点间的最短距离。已知n阶加权简单图G，设D(dij)mn是图G的边权矩阵，即dij(i,

17、j)(若G是有向图，则dij),若结点i到结点j无边相连时，则取dij。然后依次计算出矩阵D2,D3,Dn及S第20页，本讲稿共36页7.4.2Floyd算法其中D2D*D()nnd(2)ij=mindi1+d1j，di2+d2j，dindnjd(2)ij表示从vi出发两步可以到达vi的道路中距离最短者。D3D2*D()nnd(k)ij表示从vi出发k步可以到达vj的道路中距离最短者DnDn-1*D()nnSDD2D3Dn(Sij)nn由定义可知dijk表示从结点i到j经k边的路（在有向图中即为有向路）中的长度最短者，而Sij为结点i到j的所有路（若是有向图即为有向路）中的长度最短者。Floy

18、d算法的时间复杂性是O(n4)。第21页，本讲稿共36页7.4.2Floyd算法v求下图各点间的最短路径213465121733621D 1 2 1 2 1 3 7 1 3 7 1 2 1 2 3 3 6 6 1 2 3 4 5 6123456第22页，本讲稿共36页7.4.2Floyd算法v解：D(2)1 2 1 2 1 3 7 1 3 7 1 2 1 2 3 3 6 6 1 2 1 2 1 3 7 1 3 7 1 2 1 2 3 3 6 6 *2 3 4 8 2 3 4 8 2 3 6 2 3 6 4 4 d14min+,1+3,2+1,+,+,+,第23页，本讲稿共36页7.4.2Flo

19、yd算法v类似可得：3 4 6 3 4 6 5 5 D(3)D(5)D(4)6 6 第24页，本讲稿共36页7.4.2Floyd算法v所以：SDD(2)D(3)D(4)D(5)(sij)66S 1 2 3 4 6 1 2 3 4 6 1 2 3 5 1 2 3 5 1 2 4 1 2 4 3 3 6 6 213465121733621第25页，本讲稿共36页7.4.3Floyd-Warshall算法Floyd-Warshall算法是解决任意两点间的最短路径的一种算法。v基本思想：通过求解矩阵序列D(0)，D(1)，D(n)来实现问题的求解。第26页，本讲稿共36页7.4.3Floyd-Wars

20、hall算法其中：D(0)图的距离矩阵；D(n)最终解；dij边(vi,vj)的权值d(k)ij从vi到vj在所经过的顶点号k最短路径长度。即通过依次比较顶点修改路径实现求解的。对于任意两个顶点vi，vj，对于新比较的顶点vk一旦出现d(k-1)ijdikdkj，则修改对应的d(k)ij。第27页，本讲稿共36页7.4.3Floyd-Warshall算法v例：求下图各点间的最短路径213465121733621D 1 2 1 2 1 3 7 1 3 7 1 2 1 2 3 3 6 6 1 2 3 4 5 6123456第28页，本讲稿共36页7.4.3Floyd-Warshall算法v解：比较

21、经过顶点号1的矩阵213465121733621D(0)1 2 1 2 1 3 7 1 3 7 1 2 1 2 3 3 6 6 1 2 3 4 5 6123456D(1)1 2 1 2 1 3 7 1 3 7 1 2 1 2 3 3 6 6 1 2 3 4 5 6123456无改变第29页，本讲稿共36页7.4.3Floyd-Warshall算法v解：比较经过顶点号2的矩阵213465121733621D(1)1 2 1 2 1 3 7 1 3 7 1 2 1 2 3 3 6 6 1 2 3 4 5 6123456D(2)1 2 1 2 1 3 7 1 3 7 1 2 1 2 3 3 6 6

22、1 2 3 4 5 612345648d(1)14d12d24所以修改d(2)14d(1)16d12d26所以修改d(2)16第30页，本讲稿共36页7.4.3Floyd-Warshall算法v解：比较经过顶点号3的矩阵213465121733621D(2)1 2 4 8 1 2 4 8 1 3 7 1 3 7 1 2 1 2 3 3 6 6 1 2 3 4 5 6123456D(3)1 2 4 8 1 2 4 8 1 3 7 1 3 7 1 2 1 2 3 3 6 6 1 2 3 4 5 61234564233d(2)14d13d34d(2)15d13d35d(2)24d23d34d(2)2

23、5d23d35第31页，本讲稿共36页7.4.3Floyd-Warshall算法v解：比较经过顶点号4的矩阵213465121733621D(3)1 2 3 4 8 1 2 3 4 8 1 2 3 7 1 2 3 7 1 2 1 2 3 3 6 6 1 2 3 4 5 6123456D(4)1 2 2 4 8 1 2 2 4 8 1 2 3 7 1 2 3 7 1 2 1 2 3 3 6 6 1 2 3 4 5 6123456654d(3)16d13d34d46d(3)26d23d34d46d(3)36d34d46第32页，本讲稿共36页7.4.3Floyd-Warshall算法v解：比较经过

24、顶点号5的矩阵213465121733621D(4)1 2 3 4 6 1 2 3 4 6 1 2 3 5 1 2 3 5 1 2 4 1 2 4 3 3 6 6 1 2 3 4 5 6123456D(5)1 2 3 4 6 1 2 3 4 6 1 2 3 5 1 2 3 5 1 2 4 1 2 4 3 3 6 6 1 2 3 4 5 6123456无改变第33页，本讲稿共36页7.4.3Floyd-Warshall算法v解：比较经过顶点号6的矩阵213465121733621D(5)1 2 3 4 6 1 2 3 4 6 1 2 3 5 1 2 3 5 1 2 4 1 2 4 3 3 6 6

25、 1 2 3 4 5 6123456D(6)1 2 3 4 6 1 2 3 4 6 1 2 3 5 1 2 3 5 1 2 4 1 2 4 3 3 6 6 1 2 3 4 5 6123456无改变第34页，本讲稿共36页7.4.3Floyd-Warshall算法D(6)就是最终解，可以看到，和Floyd方法求得的结果是一样的。1 2 3 4 6 1 2 3 4 6 1 2 3 5 1 2 3 5 1 2 4 1 2 4 3 3 6 6 1 2 3 4 5 6123456S 1 2 3 4 6 1 2 3 4 6 1 2 3 5 1 2 3 5 1 2 4 1 2 4 3 3 6 6 D(6)第35页，本讲稿共36页7.4.3Floyd-Warshall算法Warshall算法算法求有向网络求有向网络 G=(V,E)中任两点间距离。中任两点间距离。设设D为为G的距离矩阵，的距离矩阵，n=|V|。1.输入输入D矩阵矩阵2.k 13.i 14.dij mindij,dik+dkj，j=1.n5.i i+1，若，若 i n，转，转 46.k k+1，若，若 k n，转，转 37.Stop计算复杂度计算复杂度 O(n3)第36页，本讲稿共36页