《动态规划所有点对的最短距离.ppt》由会员分享，可在线阅读，更多相关《动态规划所有点对的最短距离.ppt（33页珍藏版）》请在三一办公上搜索。
1、第七章动态规划,7.5所有点对的最短路径问题,对于一个各边权值均大于0的有n个顶点的带权有向图G=(V,E)，求所有顶点之间的最短路径和最短距离。,图的邻接矩阵表示法,3,V=,(,b,),(,a,),2,9,6,123,L=,0 2 9 0 61 0,复习Dijkstra算法,其基本思想是，设置顶点集合S并不断地作贪心选择来扩充这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。初始时，S中仅含有源点。设u是G的某一个顶点，把从源点到u且中间只经过S中顶点的路称为从源到u的特殊路径，并用数组distance记录当前每个顶点所对应的最短特殊路径长度。Dijkstra算法每次从V
2、-S中取出具有最短特殊路长度的顶点u，将u添加到S中，同时对数组distance作必要的修改。一旦S包含了所有V中顶点，distance就记录了从源到所有其它顶点之间的最短路径长度。,算法中，我们不断更新以下三个数组：s数组:si，当顶点i加入S时，si置1Distance数组:Distancei记录原点到 顶点i的最短特殊路径长度。path数组：pathi记录顶点i在其最短特殊路径上的前驱顶点。由该数组可求得原点到各点的最短路径。如：设源点是顶点1,path数组如下,例如，对右图中的有向图，应用Dijkstra算法计算从源顶点1到其它顶点间最短路径的过程列在下页的表中。,s:,distanc
3、e:,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)。,该问题具有最优子结构性质,例如上图中，若路
4、线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=m
5、indi,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的过程，主要考
6、虑的是顶点k的加入会引起什么变化？由不允许路过顶点k到允许路过顶点k，有些点间的距离是否会变的更近。,例：考虑下图所示的带权有向图，求所有顶点之间的最短距离。,V=,(,b,),(,a,),123,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）不经过
7、顶点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*)
8、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的编辑距离，记
9、为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的距离 Dijkstr
10、a算法每次从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
11、,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到其他顶点的最
12、短距离和最短路径,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;,拦截导弹 某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数），计算这套系统最多能拦截多少导弹.样例：INPUT OUTPUT 389 207 155 300 299 170 158 65 6（最多能拦截的导弹数）,本质：求最长单调不增序列,
