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

第七章动态规划,7.5所有点对的最短路径问题,对于一个各边权值均大于0的有n个顶点的带权有向图G=(V,E)，求所有顶点之间的最短路径和最短距离。,图的邻接矩阵表示法,3,V =,(,b,),(,a,),2,9,6,1 2 3,L=,0 2 9 0 6 1 0,复习Dijkstra算法,其基本思想是，设置顶点集合S并不断地作贪心选择来扩充这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。 初始时，S中仅含有源点。设u是G的某一个顶点，把从源点到u且中间只经过S中顶点的路称为从源到u的特殊路径，并用数组distance记录当前每个顶点所对应的最短特殊路径长度。Dijkstra算法每次从V-S中取出具有最短特殊路长度的顶点u，将u添加到S中，同时对数组distance作必要的修改。一旦S包含了所有V中顶点，distance就记录了从源到所有其它顶点之间的最短路径长度。,算法中，我们不断更新以下三个数组： s数组: si，当顶点i加入S时，si置1 Distance数组: Distancei记录原点到 顶点i的最短特殊路径长度。 path数组： pathi记录顶点i在其最短特殊路径上的前驱顶点。由该数组可求得原点到各点的最短路径。如：设源点是顶点1, path数组如下,例如，对右图中的有向图，应用Dijkstra算法计算从源顶点1到其它顶点间最短路径的过程列在下页的表中。,s:,distance:,path:,由源点1到顶点5的路径为：1-4-3-5,方法一：重复调用Dijkstra算法n次,可轮流以每一个顶点为源点，重复调用狄克斯特拉算法函数Dijkstra() n次，即可求得所有顶点之间的最短路径和最短距离。 利用Dijkstra()函数求所有顶点之间的最短路径算法如下。其中，distanceij中存放着从顶点i到顶点j的最短距离，pathij中存放着从顶点i到顶点j的最短路径的前一顶点下标。,voidShortPath(AdjMWGraph ,由于狄克斯特拉算法的时间复杂度是O(n2)，所以n次调用狄克斯特拉算法的时间复杂度是O(n3)。,该问题具有最优子结构性质,例如上图中，若路线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的距离。 即原问题,递推关系的建立,由di,jk-1推出di,jk的过程如下 若k=0, di,jk=Lij (因为从i到j不允许经过任何其他顶点） 若1k n, di,jk=mindi,jk-1 , di,kk-1 +dk,jk-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的距离di,jk =i到k的距离di,kk-1 + k到j的距离dk,jk-1 如果顶点i到顶点j从顶点k走更远，甚至走不通，则保持原来的距离不变 di,jk =di,jk-1 。,由di,jk-1推出di,jk的过程，主要考虑的是顶点k的加入会引起什么变化？由不允许路过顶点k到允许路过顶点k，有些点间的距离是否会变的更近。,例：考虑下图所示的带权有向图，求所有顶点之间的最短距离。,V =,(,b,),(,a,),1 2 3,L=,计算过程,Di,jk：从顶点i（可以经过顶点1、顶点2、顶点k）到顶点j的距离。,在D1中，第1行和第一列是不变的，因为说从顶点1到顶点j或顶点j到顶点1：允许经过顶点1是没有意义的,D123:从顶点2到顶点3的距离（可以经过顶点1）（1）不经过顶点1： 仍是D023=6； （2）过顶点1： D021+D013=8+9=17 取最小值6,D132:从顶点3到顶点2的距离（可以经过顶点1）（1）不经过顶点1： 仍是D032= ； （2）过顶点1： D031+D012=1+2=3 取最小值3,D213:从顶点1到顶点3的距离（也可以经过顶点2）（1）不经过顶点2： 仍是D113=9； （2）过顶点2： D112+D123=2+6=8 取最小值8,算法设计,重要发现：在从Dk-1到Dk的计算过程中中，第k行和第k列是不变的。（因为说从顶点k到顶点j或顶点j到顶点k允许经过顶点k是没有意义的）,而在从Dk-1到Dk的计算过程中也只用到第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;kn;k+) for(i=0;in;i+) for(j=0;jn;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到其它顶点间最短路径。,用邻接矩阵表示如右图：,Dijkstra算法的选择策略,开始时集合S中只有一个点，即源 用disti存储源点到顶点i的距离 Dijkstra算法每次从S外选取距离源点最近的顶点u，添加到S中，同时修改源点到S外的点最短距离dist数组。一旦S包含了所有V中顶点，dist就记录了从源到所有其它顶点之间的最短路径长度。,8.3 单源最短路径,Dijkstra算法的迭代过程：,初始状态下，S中只有一个点（源点v1）。,s:,dist:,path:,Si为顶点i是否属于集合S,disti为源到顶点i的最短特殊路径长度,pathi为顶点i的最优前驱顶点,第二步，将S外距离S最近的点v2加入S。更新相应信息。,s:,dist:,path:,1,60,2,第三步，将S外距离S最近的点v4加入S。更新相应信息。,s:,dist:,path:,1,50,4,90,4,第四步，将S外距离S最近的点v3加入S。更新相应信息。,s:,dist:,path:,1,60,3,第五步，将S外距离S最近的点v5加入S。更新相应信息。,s:,dist:,path:,1,void Dijkstra ( int GN,int v0,int dist, int path，int n) /源点v0到其他顶点的最短距离dist和最短路径下标path int *s=new intn; 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 intn; int minDis , i, j, u; /初始化三个数组 for(i=0;in;i+) ,disti=Gv0i; si=0; if(I != v0 j+),if(sj=0j+) if( sj=0&GujMAX& distu+Gujdistj ),distj=distu+Guj; pathj=u; ,拦截导弹 某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一