动态规划所有点对的最短距离

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第七章动态规划,7.5,所有点对的最短路径问题,对于一个各边权值均大于,0,的有,n,个顶点的带权有向图,G=(V,E),，,求所有顶点之间的最短路径和最短距离。,图的,邻接矩阵表示法,1,2,3,V =,(,b,),(,a,),2,8,1,9,6,1,2,3,L=,0 2 9,0 6,1 0,复习,Dijkstra,算法,其,基本思想,是，设置顶点集合,S,并不断地作,贪心选择,来扩充这个集合。一个顶点属于集合,S,当且仅当从源到该顶点的最短路径长度已知。,初始时，,S,中仅含有源点。设,u,是,G,的某一个顶点，把从源点到,u,且中间只经过,S,中顶点的路称为从源到,u,的特殊路径，并用数组,dist,ance,记录当前每个顶点所对应的最短特殊路径长度。,Dijkstra,算法每次从,V-S,中取出具有最短特殊路长度的顶点,u,，将,u,添加到,S,中，同时对数组,dist,ance,作必要的修改。一旦,S,包含了所有,V,中顶点，,dist,ance,就记录了从源到所有其它顶点之间的最短路径长度。,算法中，我们不断更新以下三个数组：,s,数组,:,si,，当顶点,i,加入,S,时，,si,置,1,Distance,数组,:,Distancei,记录原点到 顶点,i,的最短特殊路径长度。,path,数组：,pathi,记录顶点,i,在其最短特殊路径上的前驱顶点。由该数组可求得原点到各点的最短路径。如：设源点是顶点,1, path,数组如下,例如,，对右图中的有向图，应用,Dijkstra,算法计算从源顶点,1,到其它顶点间最短路径的过程列在下页的表中。,0,1,4,1,3,0,10,50,30,60,1,1,1,1,1,s:,distance:,path:,由源点,1,到顶点,5,的路径为：,1-4-3-5,方法一：重复调用,Dijkstra,算法,n,次,可轮流以每一个顶点为源点，重复调用狄克斯特拉算法函,数,Dijkstra,() n,次，即可求得所有顶点之间的最短路径和最短距离。,利用,Dijkstra,(),函数求所有顶点之间的最短路径算法如下。其中，,distanceij,中存放着从顶点,i,到顶点,j,的最短距离，,pathij,中存放着从顶点,i,到顶点,j,的,最短路径的前一顶点下标。,voidShortPath(AdjMWGraph,&G,int,*distance,int,*path),Int,n=,G.NumOfVertices,();,for(inti,=0;in;i+),Dijkstra(G,i,distance,i,path,i,);,由于狄克斯特拉算法的时间复杂度是,O(n,2,),，,所以,n,次调用狄克斯特拉算法的时间复杂度是,O(n,3,),。,该,问题具有最优子结构性质,例如上图中，若路线,I,和,J,是,A,到,C,的最优路径，则根据最优化原理，路线,J,必是从,B,到,C,的最优路线。,子,问题的构造,原,问题：每个顶点到其他所有顶点的最短距离,最小的子问题,D0,：,从顶点,i,（,不得经过任何其他顶点）到顶点,j,的距离；,子问题,D1,：,从顶点,i,（,可以经过顶点,1,，不得经过其他任何其他顶点）到顶点,j,的距离。,子问题,Dk,：,从顶点,i,（,可以经过顶点,1,、顶点,2,、,顶点,k,，,不得经过任何其他顶点）到顶点,j,的距离。,子问题,Dn,：,从顶点,i,（,可以经过顶点,1,、顶点,2,、,顶点,n,）,到顶点,j,的距离。,即原问题,递推关系的建立,由,d,i,j,k-1,推出,d,i,j,k,的过程如下,若,k=0,d,i,j,k,=Lij,(,因为从,i,到,j,不允许经过任何其他顶点）,若,1k n,d,i,j,k,=mind,i,j,k-1, d,i,k,k-1,+d,k,j,k-1,子问题,Dk-1,：,从顶点,i,（,可以经过顶点,1,、顶点,2,、,、顶点,k-1,）,到顶点,j,的距离。,子问题,Dk,：,从顶点,i,（,可以经过顶点,1,、顶点,2,、,顶点,k-1,、,顶点,k,）,到顶点,j,的距离。,从子问题,Dk-1,：,到子问题,Dk,，,仅仅多考虑了一个,顶点,k,。,我们需要重新考虑从,i,到,j,的距离：,顶点,i,到顶点,j,，,是不是从,k,走会更近？,如果从顶点,i,到顶点,j,从顶点,k,走更近，则,i,到,j,的距离,d,i,j,k,=,i,到,k,的距离,d,i,k,k-1,+,k,到,j,的距离,d,k,j,k-1,如果顶点,i,到顶点,j,从顶点,k,走更远，甚至走不通，则保持原来的距离不变,d,i,j,k,=d,i,j,k-1,。,由,d,i,j,k-1,推出,d,i,j,k,的过程，主要考虑的是顶点,k,的加入会引起什么变化？由不允许路过顶点,k,到允许路过顶点,k,，有些点间的距离是否会变的更近。,例：考虑下图所示的带权有向图，求所有顶点之间的最短距离。,V =,(,b,),(,a,),1,2,3,2,8,1,9,6,1,2,3,L=,0 2 9,0 6,1 0,计算过程,1,2,3,2,8,1,9,6,0 2 9,0 6,1 0,D,0,=,0 2 9,8,0 6,1,3 0,D,1,=,0,2,8,8 0 6,1,3,0,D,2,=,0 2,8,7 0,6,1 3 0,D,3,=,D,i,j,k,：,从顶点,i,（,可以经过顶点,1,、顶点,2,、,顶点,k,）,到顶点,j,的距离。,在,D1,中，第,1,行和第一列是不变的，因为说从,顶点,1,到顶点,j,或顶点,j,到顶点,1,：,允许经过顶点,1,是没有意义的,D,1,23:,从顶点,2,到顶点,3,的距离（可以经过顶点,1,）（,1,）不经过顶点,1,： 仍是,D,0,23=6,；,（,2,）,过顶点,1,：,D,0,21+D,0,13=8+9=17,取最小值,6,D,1,32:,从顶点,3,到顶点,2,的距离（可以经过顶点,1,）（,1,）不经过顶点,1,： 仍是,D,0,32=,；,（,2,）,过顶点,1,：,D,0,31+D,0,12=1+2=3,取最小值,3,D,2,13:,从顶点,1,到顶点,3,的距离（也可以经过顶点,2,）（,1,）不经过顶点,2,： 仍是,D,1,13=9,；,（,2,）,过顶点,2,：,D,1,12+D,1,23=2+6=8,取最小值,8,算法设计,重要发现：在从,D,k-1,到,D,k,的计算过程中中，第,k,行和第,k,列是不变的。（,因为说从,顶点,k,到顶点,j,或顶点,j,到顶点,k,允许经过顶点,k,是没有意义的）,而在从,D,k-1,到,D,k,的计算过程中也只用到第,k,行和第,k,列，也就是说，在这一步的计算过程中用到的数据都不会被覆盖。,故在算法中仅使用一个矩阵,D,即可,FLOYD,算法,FLOYD(int,*,L,int,n),int,*D=(,int,*)malloc(n+1)*(n+1)*,sizeof(int,);,D L ,将数组,L,复制到,D;,for(k,=0;k,n;k,+),for(i,=0;i,n;i,+),for(j,=0;j,n;j,+),Di,*,n+j,=,min(Di,*,n+j,Di,*,n+k+Dk,*,n+j,);,练习,有四种面值的硬币：,1,分,5,分,7,分,11,分，要找钱,15,分，最少要找多少个硬币？,用动态规划来解决,选做题,1,、设,A,和,B,是两个字符串。我们要用最少的字符操作将字符串,A,转换为字符串,B,。这里所说的字符串操作包括：,（,1,） 删除一个字符；,（,2,） 插入一个字符；,（,3,） 将一个字符改为另一个字符；,将字符串,A,变换为字符串,B,所用的最少字符操作成为字符串,A,到字符串,B,的编辑距离，记为,d(A,B,),。试设计一个有效算法，对任给的两个字符串,A,和,B,，求他们的编辑距离,d(A,B,),A=“,abcde”,B,=“,acdefa,”,4,单源最短路径,给定带权有向图,G =(V,E),，其中每条边的权是非负实数。另外，还给定,V,中的一个顶点，称为,源,。现在要计算从源到所有其它各顶点的,最短路长度,。这里路的长度是指路上各边权之和。这个问题通常称为,单源最短路径问题,。,8.3,单源最短路径,例如,，对右图中的有向图，应用,Dijkstra,算法计算从源顶点,1,到其它顶点间最短路径。,0 10,30,100,0 50, ,0,10,20 0 60, ,0,用邻接矩阵表示如右图：,Dijkstra,算法的选择策略,开始时集合,S,中只有一个点，即源,用,disti,存储源点到顶点,i,的距离,Dijkstra,算法每次从,S,外选取距离源点最近的顶点,u,，添加到,S,中，同时修改源点到,S,外的点最短距离,dist,数组。一旦,S,包含了所有,V,中顶点，,dist,就记录了从源到所有其它顶点之间的最短路径长度。,8.3,单源最短路径,迭代,S,u,dist2,dist3,dist4,dist5,初始,1,-,10,maxint,30,100,1,1,2,2,10,60,30,100,2,1,2,4,4,10,50,30,90,3,1,2,4,3,3,10,50,30,60,4,1,2,4,3,5,5,10,50,30,60,Dijkstra,算法的迭代过程：,初始状态下，,S,中只有一个点（源点,v1,）。,-1,1,-1,1,1,0,10,30,100,1,0,0,0,0,s:,dist:,path:,Si,为顶点,i,是否属于集合,S,disti,为源到顶点,i,的最短特殊路径长度,pathi,为顶点,i,的最优前驱顶点,第二步，将,S,外距离,S,最近的点,v2,加入,S,。更新相应信息。,-1,1,-1,1,1,0,10,30,100,1,0,0,0,0,s:,dist:,path:,1,60,2,第三步，将,S,外距离,S,最近的点,v4,加入,S,。更新相应信息。,-1,1,2,1,1,0,10,60,30,100,1,1,0,0,0,s:,dist:,path:,1,50,4,90,4,第四步，将,S,外距离,S,最近的点,v3,加入,S,。更新相应信息。,-1,1,4,1,4,0,10,50,30,90,1,1,0,1,0,s:,dist:,path:,1,60,3,第五步，将,S,外距离,S,最近的点,v5,加入,S,。更新相应信息。,-1,1,4,1,3,0,10,50,30,60,1,1,1,1,0,s:,dist:,path:,1,void,Dijkstra,(,int,GN,int,v0,int dist,int,path,，,int,n),/,源点,v0,到其他顶点的最短距离,dist,和最短路径下标,path,int,*s=new,int,n,;,int,minDis, i, j, u;,/,初始化三个数组,/,逐次将各点加入,S,/,在当前还未找到最短路径的顶点集中 选取具有最短距离的顶点,u,/,标记顶点,u,已从集合,T,加入到集合,S,中,/,修改从,v0,到其他顶点的最短距离和最短路径,void,Dijkstra,(,int,GN,int,v0,int dist,int,path,，,int,n),/,从源点,v0,到其他顶点的最短距离,dist,和最短路径下标,path,int,*s=new,int,n,;,int,minDis, i, j, u;,/,初始化三个数组,for(i=0;in;i+),dist,i,=Gv0i;,s,i,=0;,if(I,!= v0 & dist,i,MAX) path,i,=v0;,else path,i,=-1;,s,v0,=1,;/,标记顶点,v0,已从集合,T,加入到集合,S,中,/,在当前还未找到最短路径的顶点集中选取具有最短距离的顶点,u,for(i=1;in;i+),minDis,=MAX;,for(j=0;j=n;j+),u,到,j,有边相连，,j,才有可能因,u,的加入而距离源点更近,if(s,j,=0&dist,j,minDis,),u=j;,minDis,=dist,j,;,s,u,=1;/,标记顶点,u,已从集合,T,加入到集合,S,中,/,修改从,v0,到其他顶点的最短距离和最短路径,for(j=0;jn;j+),if(,sj,=0&GujMAX&,distu+Guj,distj, ),distj,=,distu+Guj,;,pathj,=u;,拦截导弹,某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。,输入导弹依次飞来的高度（雷达给出的高度数据是不大于,30000,的正整数），计算这套系统最多能拦截多少导弹,.,样例：,INPUT OUTPUT,389 207 155 300 299 170 158 65 6,（最多能拦截的导弹数）,本质：求最长单调不增序列,