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

1、第七章动态规划第七章动态规划7.5所有点对的最短路径问题 对于一个各边权值均大于0的有n个顶点的带权有向图G=(V,E)，求所有顶点之间的最短路径和最短距离。图的邻接矩阵表示法123V =( b )( a )28196123L= 0 2 9 0 68 1 0复习Dijkstra算法 其其基本思想基本思想是，设置顶点集合是，设置顶点集合S S并不断地作并不断地作贪心选择贪心选择来扩充这个集合。一个顶点属于集合来扩充这个集合。一个顶点属于集合S S当且仅当从源到该顶点的最短路径长度已知。当且仅当从源到该顶点的最短路径长度已知。初始时，初始时，S S中仅含有源点。设中仅含有源点。设u u是是G G的

2、某一个的某一个顶点，把从源点到顶点，把从源点到u u且中间只经过且中间只经过S S中顶点的路中顶点的路称为从源到称为从源到u u的特殊路径，并用数组的特殊路径，并用数组distdistance记记录当前每个顶点所对应的最短特殊路径长度。录当前每个顶点所对应的最短特殊路径长度。DijkstraDijkstra算法每次从算法每次从V-SV-S中取出具有最短特殊路中取出具有最短特殊路长度的顶点长度的顶点u u，将，将u u添加到添加到S S中，同时对数组中，同时对数组distdistance作必要的修改。一旦作必要的修改。一旦S S包含了所有包含了所有V V中顶中顶点，点，distdistance就

3、记录了从源到所有其它顶点之间就记录了从源到所有其它顶点之间的最短路径长度。的最短路径长度。 算法中，我们不断更新以下三个数组： s数组: si，当顶点i加入S时，si置1 Distance数组: Distancei记录原点到 顶点i的最短特殊路径长度。 path数组： pathi记录顶点i在其最短特殊路径上的前驱顶点。由该数组可求得原点到各点的最短路径。如：设源点是顶点1, path数组如下例如例如，对右图中的有向图，应用Dijkstra算法计算从源顶点1到其它顶点间最短路径的过程列在下页的表中。0141301050306011111s:distance:path:由源点1到顶点5的路径为：1

4、-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,di

5、stancei,pathi); 由于狄克斯特拉算法的时间复杂度是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

6、 ）到顶点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：到子问题

7、：到子问题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的过程，主要考虑的是顶点的过程，

8、主要考虑的是顶点k的加入会引起什么变化？由不允许路过顶点的加入会引起什么变化？由不允许路过顶点k到允许路过顶点到允许路过顶点k，有些点间的距离是否会，有些点间的距离是否会变的更近。变的更近。 例：考虑下图所示的带权有向图，求所有顶点之间的最短距离。V =( b )( a )12328196123L= 0 2 9 0 68 1 0计算过程123281960 2 9 0 68 1 0D0 =0 2 98 0 61 3 0D1 =0 2 88 0 61 3 0D2 =0 2 87 0 61 3 0D3 =Di,jk：从顶点：从顶点i（可以经过顶点（可以经过顶点1、顶点、顶点2、顶点顶点k）到顶点）到

9、顶点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=3 取最小值3D213:从顶点1到顶点3的距离（也可以经过顶点2）（1）不经过顶点2： 仍是D113=9；（2）过顶点2： D112+D123=2+6=8 取最小值8算法设计重要发现：在从重

10、要发现：在从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)

11、*(n+1)*sizeof(int); D L 将数组L复制到D; for(k=0;kn;k+) for(i=0;in;i+) for(j=0;j16S4=5v4=9子问题的构造 当n=1时:只有一个物品， s1=2,v1=3 若背包容量c=0、1，则无法装入物品1，得到背包价值为0若背包容量c=2、3、4、5、6，7，8，9则可装入物品1，得到背包价值为3。 C10=0 C11=0 C12=3 C13=3 C14=3 C15=3 C16=3 C17=3 C18=3 C19=3考虑两个物品的情况 当n=2时，有两个物品， s1=2,v1=3，s2=3,v2=7 若背包容量c=0、1，得到背包价

12、值为0若背包容量c=2，可装入物品1，得总价值m22=3若背包容量c=3，m23=7若背包容量c=4, m24=7若背包容量c=5, m25=10若不装物品2，m23=m13=3若装入物品2，m23=v2+m13-3=7+0=7m26=10 m27=10 m28=10 m29=10 若不装物品2，m25=m15=3若装入物品2，m25=v2+m15-3=7+3=7递推关系的建立 用mij来表示从前i个物品中选取物品装入容量为j的背包所得的最大价值。则要寻求的是mnc。 mij是以下两个值的最大值（1） mi-1j: 即不装入物品i,背包价值与仅考虑前i-1个物品时情况相同； （2）vi+mi-

13、1j-si:即装入物品i,再从前i-1个物品中选取，使背包剩余容积j-si价值最大化。构造价值数组S1=2v1=3S2=3v2=7S3=4v3=5S4=5v4=9S5=4v5=8012345678900000000000100333333332003771010101010300377101012121240037710101216165018背包容量j从前i个物品中选取S1=2v1=3S2=3v2=7S3=4v3=5S4=5v4=9S5=4v5=80123456789000000000001003333333320037710101010103003771010121215400377101

14、01216165018背包容量j从前i个物品中选取构造最优解012345678900000000000100333333332003771010101010300377101012121540037710101216165003781011151618因m59m49, 物品5被装入，剩余c=9-s5=5因m45m35, 物品4被装入，剩余c=9-s4=0 void Knapsack(int t v,int w,int c,int n,float mN)/构造价值数组m int i, j;for(i=0; i=n; i+)mi0=0;for(j=0; j=c; j+)m0j=0;for(i=1;

15、 n; i+) /计算前计算前n-1行行 for(j=1; jwi; j+) mij= mi-1j; for(j= wi; j mi-1j) mij=t; else mij=mi-1j; /计算最后一行的mnct= vn+ mn-1c-wn;If ( t mn-1c ) mnc=telse mnc=mn-1c; void Trackback(int mN, int w, int c, int n, int x)int i,j;for(i=n;i0;i-) if(mic=mi-1c) xi=0 else xi=1;c=c-wi; 上机作业 编程求解0-1背包问题P140的练习 7.4 A=“xz

16、yzzyx”, B=“zxyyzxz”,求A和B 的最长公共子序列 7.9 7.21 练习 有四种面值的硬币：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” 拦截导弹拦截导弹 某国为了防御敌