《动态规划所有点对的最短距离课件》由会员分享，可在线阅读，更多相关《动态规划所有点对的最短距离课件（33页珍藏版）》请在金锄头文库上搜索。
1、第第七七章章动动态态规规划划动态规划所有点对的最短距离课件7.5所有点对的最短路径问题对于一个各边权值均大于0的有n个顶点的带权有向图G=(V,E)，求所有顶点之间的最短路径和最短距离。图的邻接矩阵表示法123V =(b )(a )28196123L= 029806910动态规划所有点对的最短距离课件复习Dijkstra算法 其其基本思想基本思想是，设置顶点集合是，设置顶点集合S S并不断地作并不断地作贪贪心选择心选择来扩充这个集合。一个顶点属于集合来扩充这个集合。一个顶点属于集合S S当当且仅当从源到该顶点的最短路径长度已知。且仅当从源到该顶点的最短路径长度已知。初始时，初始时，S S中仅含
2、有源点。设中仅含有源点。设u u是是G G的某一个顶的某一个顶点，把从源点到点，把从源点到u u且中间只经过且中间只经过S S中顶点的路称为中顶点的路称为从源到从源到u u的特殊路径，并用数组的特殊路径，并用数组distdistance记录当记录当前每个顶点所对应的最短特殊路径长度。前每个顶点所对应的最短特殊路径长度。DijkstraDijkstra算法每次从算法每次从V-SV-S中取出具有最短特殊路中取出具有最短特殊路长度的顶点长度的顶点u u，将，将u u添加到添加到S S中，同时对数组中，同时对数组distdistance作必要的修改。一旦作必要的修改。一旦S S包含了所有包含了所有V
3、V中顶中顶点，点，distdistance就记录了从源到所有其它顶点之间就记录了从源到所有其它顶点之间的最短路径长度。的最短路径长度。动态规划所有点对的最短距离课件算法中，我们不断更新以下三个数组：s数组:si，当顶点i加入S时，si置1Distance数组:Distancei记录原点到顶点i的最短特殊路径长度。path数组：pathi记录顶点i在其最短特殊路径上的前驱顶点。由该数组可求得原点到各点的最短路径。如：设源点是顶点1,path数组如下动态规划所有点对的最短距离课件例如例如，对右图中的有向图，应用Dijkstra算法计算从源顶点1到其它顶点间最短路径的过程列在下页的表中。014130
4、1050306011111s: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
5、)Intn=G.NumOfVertices();for(inti=0;in;i+)Dijkstra(G,i,distancei,pathi);由于狄克斯特拉算法的时间复杂度是O(n2)，所以n次调用狄克斯特拉算法的时间复杂度是O(n3)。动态规划所有点对的最短距离课件该问题具有最优子结构性质 例如上图中，若路线I和J是A到C的最优路径，则根据最优化原理，路线J必是从B到C的最优路线。动态规划所有点对的最短距离课件子问题的构造原问题：每个顶点到其他所有顶点的最短距离最小的子问题D0：从顶点i（不得经过任何其他顶点）到顶点j的距离；子问题D1：从顶点i（可以经过顶点1，不得经过其他任何其他顶点）到
6、顶点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
7、-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 如果顶点如果顶点
8、i到顶点到顶点j从顶点从顶点k走更远，甚至走不通，走更远，甚至走不通，则保持原来的距离不变则保持原来的距离不变 di,jk =di,jk-1。由由di,jk-1推出推出di,jk的过程，主要考虑的是顶点的过程，主要考虑的是顶点k的加入会引起什么变化？由不允许路过顶点的加入会引起什么变化？由不允许路过顶点k到允许路过顶点到允许路过顶点k，有些点间的距离是否会，有些点间的距离是否会变的更近。变的更近。 动态规划所有点对的最短距离课件例：考虑下图所示的带权有向图，求所有顶点之间的最短距离。V =(b )(a )12328196123L= 029806910计算过程动态规划所有点对的最短距离课件123
9、28196029806910D0=029806130D1=028806130D2=028706130D3=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取最小值6D132:从顶点3到顶点2的距离（可以经过顶点1）（1）不经过顶点1：仍是D032=；（2）过顶点1：D031+D012=1+2=
10、3取最小值3D213:从顶点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列，也就是说，在这一步列，也就是说，在这一步的计算过程中用到的数据都
11、不会被覆盖。的计算过程中用到的数据都不会被覆盖。故在算法中仅使用一个矩阵故在算法中仅使用一个矩阵D即可即可动态规划所有点对的最短距离课件FLOYD算法FLOYD(int*L,intn)int*D=(int*)malloc(n+1)*(n+1)*sizeof(int);DL将数组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
12、、设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)G =(V,E)，其中每条，其中每条边的权是非负实数。另外，还给定边的权是非负实数。另外，还给定V V中的中的一个顶点，称为一个顶点
13、，称为源源。现在要计算从源到。现在要计算从源到所有其它各顶点的所有其它各顶点的最短路长度最短路长度。这里路。这里路的长度是指路上各边权之和。这个问题的长度是指路上各边权之和。这个问题通常称为通常称为单源最短路径问题单源最短路径问题。动态规划所有点对的最短距离课件8.3 单源最短路径例如例如，对右图中的有向图，应用Dijkstra算法计算从源顶点1到其它顶点间最短路径。01030100 050010200600用邻接矩阵表用邻接矩阵表示如右图：示如右图：动态规划所有点对的最短距离课件DijkstraDijkstra算法的选择策略算法的选择策略 开始时集合开始时集合S S中只有一个点，即源中只有一
14、个点，即源 用用distidisti存储源点到顶点存储源点到顶点i i的距离的距离 Dijkstra Dijkstra算法每次从算法每次从S S外选取距离源点外选取距离源点最近的顶点最近的顶点u u，添加到，添加到S S中，同时修改源点中，同时修改源点到到S S外的点最短距离外的点最短距离distdist数组。一旦数组。一旦S S包含包含了所有了所有V V中顶点，中顶点，distdist就记录了从源到所有就记录了从源到所有其它顶点之间的最短路径长度。其它顶点之间的最短路径长度。动态规划所有点对的最短距离课件8.3 单源最短路径迭代迭代S Su udist2dist2 dist3dist3 di
15、st4dist4 dist5dist5 初始初始1-10maxint301001 11,221060301002 21,2,44105030903 31,2,4,33105030604 41,2,4,3,5510503060Dijkstra算法的迭代过程： 动态规划所有点对的最短距离课件初始状态下，初始状态下，S S中只中只有一个点（源点有一个点（源点v1v1）。）。-11-1110 01010303010010010000s:dist:path:Si为顶点为顶点i是否属于集合是否属于集合Sdisti为源到顶点为源到顶点i的最短特殊路径长度的最短特殊路径长度pathi为顶点为顶点i的最优前驱顶
16、点的最优前驱顶点动态规划所有点对的最短距离课件第二步，将第二步，将S S外距离外距离S S最近的点最近的点v2v2加入加入S S。更新。更新相应信息。相应信息。-11-1110 01010303010010010000s:dist:path:1602动态规划所有点对的最短距离课件第三步，将第三步，将S S外距离外距离S S最近的点最近的点v4v4加入加入S S。更新。更新相应信息。相应信息。-112110 0101060303010010011000s:dist:path:1504904动态规划所有点对的最短距离课件第四步，将第四步，将S S外距离外距离S S最近的点最近的点v3v3加入加入S
17、 S。更新。更新相应信息。相应信息。-114140 01010503030909011010s:dist:path:1603动态规划所有点对的最短距离课件第五步，将第五步，将S S外距离外距离S S最近的点最近的点v5v5加入加入S S。更新。更新相应信息。相应信息。-114130 01010503030606011110s:dist:path:1动态规划所有点对的最短距离课件voidDijkstra(intGN,intv0,intdist,intpath，intn)/源点v0到其他顶点的最短距离dist和最短路径下标pathint*s=newintn;intminDis,i,j,u;/初始化
18、三个数组动态规划所有点对的最短距离课件/逐次将各点加入S/在当前还未找到最短路径的顶点集中选取具有最短距离的顶点u/标记顶点u已从集合T加入到集合S中/修改从v0到其他顶点的最短距离和最短路径动态规划所有点对的最短距离课件voidDijkstra(intGN,intv0,intdist,intpath，intn)/从源点v0到其他顶点的最短距离dist和最短路径下标pathint*s=newintn;intminDis,i,j,u;/初始化三个数组for(i=0;in;i+)动态规划所有点对的最短距离课件disti=Gv0i;si=0;if(I!=v0&distiMAX)pathi=v0;el
19、sepathi=-1;sv0=1;/标记顶点v0已从集合T加入到集合S中/在当前还未找到最短路径的顶点集中选取具有最短距离的顶点ufor(i=1;in;i+)minDis=MAX;for(j=0;j=n;j+)动态规划所有点对的最短距离课件u到到j有边相连，有边相连，j才有可能因才有可能因u的加的加入而距离源点更入而距离源点更近近if(sj=0&distjminDis)u=j;minDis=distj;su=1;/标记顶点u已从集合T加入到集合S中/修改从v0到其他顶点的最短距离和最短路径for(j=0;jn;j+)if(sj=0&GujMAX&distu+Gujdistj)动态规划所有点对的
20、最短距离课件distj=distu+Guj;pathj=u;动态规划所有点对的最短距离课件拦截导弹拦截导弹某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数），计算这套系统最多能拦截多少导弹.样例：INPUTOUTPUT389207155300299170158656（最多能拦截的导弹数）本质：求最长单调不增序列动态规划所有点对的最短距离课件
