图论4最短路问题课件

单击此处编辑母版文本样式,第二级,第三级,单击此处编辑母版标题样式,1,返回 结束,7.4 最短路问题,一、问题的提出,赋权图（网络）：,G=(V,E)中，给每条边,a,=赋予一个非负实数权,w,ij,，得到一个有向网络,7.4 最短路问题一、问题的提出赋权图（网络）：G=(V,7.4 最短路问题,路径,路径长度,非带权图的路径长度是指此路径上边的条数。,带权图的路径长度是指路径上各边的权之和,距离矩阵,对上述网络，定义 D=(,d,ij,),n,n,，,n,=|V|,w,ij,当,E,d,ij,=,其它,带权路径长度,对上述网络，路径,v,1,v,2,v,k,的带权路径长度定义为,7.4 最短路问题路径,7.4 最短路问题,最短路问题在实际工作中应用,1,、通讯网络中最可靠问题,2,、最大容量问题,3,、统筹方法中求关键路线,4,、背包问题,5,、选址问题,6,、工件加工顺序问题,7,、中国邮递员问题,背包问题,(Knapsack problem),是一种,组合优化,的,NP,完全问题。问题可以描述为：给定一组物品，每种物品都有自己的重量和价格，在限定的总重量内，我们如何选择，才能使得物品的总价格最高。问题的名称来源于如何选择最合适的物品放置于给定背包中。,7.4 最短路问题最短路问题在实际工作中应用1、通讯网络中,7.4 最短路问题,例,一位旅客要从A城到B城,他希望选择一条途中中转次数最少的路线；,他希望选择一条途中所花时间最短的路线；,他希望选择一条途中费用最小的路线；,v,5,v,4,v,3,v,2,v,1,v,0,100,60,30,10,10,20,5,50,这些问题均是带权图上的最短路径问题。,边上的权表示一站,边上的权代表距离,边的权代表费用,7.4 最短路问题例一位旅客要从A城到B城v5v4v3v2,7.4 最短路问题,Dijkstra算法,Floyd算法,Floyd-,Warshall算法,7.4 最短路问题Dijkstra算法,7.4 最短路问题,Dijkstra,算法,Dijkstra,算法是由荷兰计算机科学家,狄克斯特拉,（,Dijkstra,）于,1959,年提出的，因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法，解决的是有向图中最短路径问题。,荷兰计算机科学教授,Edsger W.Dijkstra(1930-),在,1972,年获得美国计算机协会授予的图灵奖，这是计算机科学中最具声望的奖项之一。,Dijkstra,算法是求出一个连通加权简单图中从结点,a,到结点,z,的最短路。边,(i,j),的权,(i,j),0,，且结点,x,的标号为,L(x),。结束时，,L(z),是从,a,到,z,的最短长度。,举例来说，如果图中的顶点表示城市，而边上的,权重,表示城市间开车行经的距离。,Dijkstra,算法可以用来找到两个城市之间的最短路径。,7.4 最短路问题Dijkstra算法 Dijk,7.4.1 Dijkstra算法,Dijkstra算法,基本思想,:,把图中所有结点分为两组，每一个结点对应一个距离值。,第一组：包括已确定最短路径的结点，结点对应的距离值是由v,0,到此结点的最短路径长度；,第二组：包括尚未确定最短路径的结点，结点对应的距离值是v,0,经由第一组结点（中间结点）至此结点的最短路径长度。,按最短路径长度递增的顺序把第二组的结点加到第一组中去，直至v,0,可达的所有结点都包含于第一组。在这个过程中，总保持从v,0,到第一组各结点的最短路径长度都不大于从v,0,至第二组任何结点的路径长度。,7.4.1 Dijkstra算法Dijkstra算法基本思,7.4.1 Dijkstra算法,设源点为v,0,初始时v,0,进入第一组，v,0,的距离值为0；第二组包含其它所有结点，这些结点对应的距离值这样确定（设v,i,为第二组中的结点）,然后每次从第二组的结点中选一个其距离值为最小的结点v,m,加到第一组中。每往第一组加入一个结点v,m,，就要对第二组的各结点的距离值作一次修正（设v,i,为第二组的结点）：,若加进v,m,做中间结点使得v,0,至v,i,的路径长度更短（即v,i,的距离值v,m,的距离值+W,mi,），则要修改v,i,的距离（v,i,的距离值v,m,的距离值+W,mi,）。修改后再选距离值最小的一个结点加入到第一组中，。如此进行下去，直至第一组囊括图的所有结点或再无可加入第一组的结点存在。显然，这种从第二组的结点中选距离值最小的结点扩展是一种贪心策略。,7.4.1 Dijkstra算法设源点为v0,7.4.1 Dijkstra算法,procedure,Dijkstra(G:所有权都为正数的加权连通简单图),G带有顶点av,0,v,1,v,n,z和权(v,i,v,j,)，若(v,i,v,j,)不是G的边，则(v,i,v,j,),for,i:1,to,n,L(v,i,),L(a):0,S:（初始化标记，a的标记为0，其余结点标记为，S是空集,while,z,S,begin,u:不属于S的L(u)最小的一个顶点,S:Su,for,所有不属于S的顶点v,if,L(u)(u,v)L(v),then,L(v):L(u)(u,v),这样就给S中添加带最小标记的顶点并且更新不在S中的顶点的标记,end,L(z)从a到z的最短长度,d,ij,7.4.1 Dijkstra算法procedure D,7.4.1 Dijkstra算法,下面给出该算法的框图：,通过框图，容易计算该算法计算量 。,7.4.1 Dijkstra算法下面给出该算法的框图：通过,7.4.1 Dijkstra算法,下面通过一个实例来说明,Dijkstra,算法是如何工作的。,7.4.1 Dijkstra算法下面通过一个实例来说明Di,7.4.1 Dijkstra算法,7.4.1 Dijkstra算法,7.4.1 Dijkstra算法,1,4,5,6,2,3,10,8,a,b,c,d,e,z,用,Dijkstra,算法求,a,和,z,之间最短路所用的步骤。,7.4.1 Dijkstra算法,7.4.1 Dijkstra算法,Dijkstra,算法,(另外一种说明),求有向网络,G=(V,A),中结点,v,1,到其它结点的最短距离。,设,D,为,G,的距离矩阵，,n=|V|,，向量,U=(u,1,u,2,u,n,),的,u,i,标记结点,v,1,到,v,i,的距离。,S,为已取得最短路的结点集合，其中每个结点在,U,中有固定标号标记取得的最短路的长度；,S,为未取得最短路的结点集合，其中每个结点在,U,中有临时标号。,7.4.1 Dijkstra算法Dijkstra算法(另外,7.4.1 Dijkstra算法,0.初始化：u,1,(1),0，,u,j,(1),d,1,j,(,j,=2,3,n),S,(1),v,1,，,S,(1),v,2,v,3,v,n,，m=1;,1.选固定标号：在,S,(m),中求,v,k,，使得,u,k,(m),=min,u,j,(m),|,v,j,S,(m),。若,u,k,(m),=，则,S,(m),中的结点无最短路径；否则转2。,2.判结束：令,S,(m+1),S,(m),v,k,S,(m+1),S,(m),v,k,若 m=n1，结束。,3.修改临时标号：对所有,v,j,S,(m+1),，令,u,j,(m+1),=min,u,j,(m),u,k,(m),+,d,kj,，m,m+1；转1。,7.4.1 Dijkstra算法0.初始化：u1(1),7.4.1 Dijkstra算法,Dijkstra算法只求出图中一个特定的顶点到其他各定点的最短路。但在许多实际问题中，需求出任意两点之间的最短路，如全国各城市之间最短的航线，选址问题等。当然，要求出一个图的任意两点间的最短距路，只需将图中每一个顶点依次视为始点，然后用Dijkstra算法就可以了。,Dijkstra算法在物流配送中的应用,OSPF（open shortest path first,开放最短路径优先）算法是Dijkstra算法在网络路由中的一个具体实现。,7.4.1 Dijkstra算法Dijkstra算法只求出,7.4.1 Dijkstra算法,Dijkstra算法要求图上的权是非负数，否则结果不正确；,Dijkstra算法同样适用于无向图，此时一个无向边次相当于两个有向边。,利用求最短路的方法求最长路。由于存在负权（求最长路和负权等价），所以在这里Dijkstra算法不适用了，必须采用,Floyd,算法-,动态规划算法,Floyd,算法的功能是通过一个图的权值矩阵求出它的每两点间的最短路径矩阵.,7.4.1 Dijkstra算法Dijkstra算法要求图,7.4.2 Floyd算法,如果有一个矩阵D=d(ij)，其中d(ij)0表示i城市到j城市的距离。若i与j之间无路可通，那么d(ij)就是无穷大。又有d(ii)=0。通过这个距离矩阵D，把任意两个城市之间的最短路径找出来。,【分析】对于任何一个城市而言，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(ik)+d(kj)，每当一个k查完了，d(ij)就是目前的 i 到 j 的最短距离。重复这一过程，最后当查完所有的k时，d(ij)里面存放的就是 i 到 j 之间的最短距离了。,7.4.2 Floyd算法如果有一个矩阵D=d(ij)，,7.4.2 Floyd算法,定义7.4.1:,已知矩阵A(a,ij,),ml,，B(b,jk,),ln,，规定CA*B(c,ij,),mn,，其中c,ij,min(a,i1,b,1j,a,i2,b,2j,a,il,b,lj,),定义7.4.2,已知矩阵A(a,ij,),mn,，B(b,ij,),mn,，规定DA B(d,ij,),mn,，其中d,ij,min(a,ij,b,ij,),可以利用上面定义的运算求任意两点间的最短距离。,已知n阶加权简单图G，设D(d,ij,),mn,是图G的边权矩阵，即d,ij,(i,j)(若G是有向图，则d,ij,),若结点i到结点 j无边相连时，则取d,ij,。然后依次计算出矩阵D,2,D,3,D,n,及S,7.4.2 Floyd算法定义7.4.1:已知矩阵A(ai,7.4.2 Floyd算法,其中 D,2,D*D(),nn,d,(2),ij,=mind,i1,+d,1j,，d,i2,+d,2j,，d,in,d,nj,d,(2),ij,表示从v,i,出发两步可以到达v,i,的道路中距离最短者。,D,3,D,2,*D(),nn,d,(k),ij,表示从v,i,出发k步可以到达v,j,的道路中距离最短者,D,n,D,n-1,*D(),nn,SD D,2,D,3,D,n,(S,ij,),nn,由定义可知dij,k,表示从结点i到j经k边的路（在有向图中即为有向路）中的长度最短者，而S,ij,为结点i到j的所有路（若是有向图即为有向路）中的长度最短者。,Floyd算法的时间复杂性是O(n4)。,7.4.2 Floyd算法其中 D2D*D(,7.4.2 Floyd算法,求下图各点间的最短路径,2,1,3,4,6,5,1,2,1,7,3,3,6,2,1,D,1 2 ,1 3 7,1 2 ,3,6,1 2 3 4 5 6,1,2,3,4,5,6,7.4.2 Floyd算法求下图各点间的最短路径213465,7.4.2 Floyd算法,解：,D,(2),1 2 ,1 3 7,1 2 ,3,6,1 2 ,1