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

第七章动态规划Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientPro.Copyright2004-2011AsposePtyLtd.17.5所有点对的最短路径问题对于一个各边权值均大于0的有n个顶点的带权有向图G=(V,E)，求所有顶点之间的最短路径和最短距离。图的邻接矩阵表示法123V=(b)(a)28196123L=

029061∞0Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientPro.Copyright2004-2011AsposePtyLtd.2复习Dijkstra算法其基本思想是，设置顶点集合S并不断地作贪心选择来扩充这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。 初始时，S中仅含有源点。设u是G的某一个顶点，把从源点到u且中间只经过S中顶点的路称为从源到u的特殊路径，并用数组distance记录当前每个顶点所对应的最短特殊路径长度。Dijkstra算法每次从V-S中取出具有最短特殊路长度的顶点u，将u添加到S中，同时对数组distance作必要的修改。一旦S包含了所有V中顶点，distance就记录了从源到所有其它顶点之间的最短路径长度。Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientPro.Copyright2004-2011AsposePtyLtd.3算法中，我们不断更新以下三个数组：s数组:s[i]，当顶点i加入S时，s[i]置1Distance数组:Distance[i]记录原点到顶点i的最短特殊路径长度。path数组：path[i]记录顶点i在其最短特殊路径上的前驱顶点。由该数组可求得原点到各点的最短路径。如：设源点是顶点1,path数组如下Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientPro.Copyright2004-2011AsposePtyLtd.4

例如，对右图中的有向图，应用Dijkstra算法计算从源顶点1到其它顶点间最短路径的过程列在下页的表中。0141301050306011111s:distance:path:由源点1到顶点5的路径为：1->4->3->5Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientPro.Copyright2004-2011AsposePtyLtd.5方法一：重复调用Dijkstra算法n次可轮流以每一个顶点为源点，重复调用狄克斯特拉算法函数Dijkstra()n次，即可求得所有顶点之间的最短路径和最短距离。利用Dijkstra()函数求所有顶点之间的最短路径算法如下。其中，distance[i][j]中存放着从顶点i到顶点j的最短距离，path[i][j]中存放着从顶点i到顶点j的最短路径的前一顶点下标。Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientPro.Copyright2004-2011AsposePtyLtd.6voidShortPath(AdjMWGraph&G,int**distance,int**path){Intn=G.NumOfVertices();for(inti=0;i<n;i++)Dijkstra(G,i,distance［i］,path［i］);}由于狄克斯特拉算法的时间复杂度是O(n2)，所以n次调用狄克斯特拉算法的时间复杂度是O(n3)。Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientPro.Copyright2004-2011AsposePtyLtd.7该问题具有最优子结构性质例如上图中，若路线I和J是A到C的最优路径，则根据最优化原理，路线J必是从B到C的最优路线。Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientPro.Copyright2004-2011AsposePtyLtd.8子问题的构造原问题：每个顶点到其他所有顶点的最短距离最小的子问题D0：从顶点i（不得经过任何其他顶点）到顶点j的距离；子问题D1：从顶点i（可以经过顶点1，不得经过其他任何其他顶点）到顶点j的距离。Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientPro.Copyright2004-2011AsposePtyLtd.9子问题Dk：从顶点i（可以经过顶点1、顶点2、……顶点k，不得经过任何其他顶点）到顶点j的距离。子问题Dn：从顶点i（可以经过顶点1、顶点2、……顶点n）到顶点j的距离。——即原问题Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientPro.Copyright2004-2011AsposePtyLtd.10递推关系的建立由di,jk-1推出di,jk的过程如下若k=0,di,jk=L[i][j](因为从i到j不允许经过任何其他顶点）若1≤k≤n,di,jk=min{di,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，有些点间的距离是否会变的更近。Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientPro.Copyright2004-2011AsposePtyLtd.11例：考虑下图所示的带权有向图，求所有顶点之间的最短距离。V=(b)(a)12328196123L=

029061∞0计算过程Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientPro.Copyright2004-2011AsposePtyLtd.1212328196029061∞0D0=029806130D1=028806130D2=028706130D3=Di,jk：从顶点i（可以经过顶点1、顶点2、……顶点k）到顶点j的距离。在D1中，第1行和第一列是不变的，因为说从顶点1到顶点j或顶点j到顶点1：允许经过顶点1是没有意义的D1[2][3]:从顶点2到顶点3的距离（可以经过顶点1）（1）不经过顶点1：仍是D0[2][3]=6；（2）过顶点1：D0[2][1]+D0[1][3]=8+9=17取最小值6D1[3][2]:从顶点3到顶点2的距离（可以经过顶点1）（1）不经过顶点1：仍是D0[3][2]=∞

；（2）过顶点1：D0[3][1]+D0[1][2]=1+2=3取最小值3D2[1][3]:从顶点1到顶点3的距离（也可以经过顶点2）（1）不经过顶点2：仍是D1[1][3]=9；（2）过顶点2：D1[1][2]+D1[2][3]=2+6=8取最小值8Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientPro.Copyright2004-2011AsposePtyLtd.13算法设计重要发现：在从Dk-1到Dk的计算过程中中，第k行和第k列是不变的。（因为说从顶点k到顶点j或顶点j到顶点k允许经过顶点k是没有意义的）

而在从Dk-1到Dk的计算过程中也只用到第k行和第k列，也就是说，在这一步的计算过程中用到的数据都不会被覆盖。故在算法中仅使用一个矩阵D即可Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientPro.Copyright2004-2011AsposePtyLtd.14FLOYD算法FLOYD(int*L,intn){int*D=(int*)malloc((n+1)*(n+1)*sizeof(int));DL{将数组L复制到D};for(k=0;k<n;k++)for(i=0;i<n;i++)for(j=0;j<n;j++)D[i*n+j]=min(D[i*n+j],D[i*n+k]+D[k*n+j]);}Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientPro.Copyright2004-2011AsposePtyLtd.15练习有四种面值的硬币：1分5分7分11分，要找钱15分，最少要找多少个硬币？用动态规划来解决Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientPro.Copyright2004-2011AsposePtyLtd.16选做题1、设A和B是两个字符串。我们要用最少的字符操作将字符串A转换为字符串B。这里所说的字符串操作包括：（1）删除一个字符；（2）插入一个字符；（3）将一个字符改为另一个字符；将字符串A变换为字符串B所用的最少字符操作成为字符串A到字符串B的编辑距离，记为d(A,B)。试设计一个有效算法，对任给的两个字符串A和B，求他们的编辑距离d(A,B)A=“abcde”,B=“acdefa”Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientPro.Copyright2004-2011AsposePtyLtd.174单源最短路径

给定带权有向图G=(V,E)，其中每条边的权是非负实数。另外，还给定V中的一个顶点，称为源。现在要计算从源到所有其它各顶点的最短路长度。这里路的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientPro.Copyright2004-2011AsposePtyLtd.188.3单源最短路径

例如，对右图中的有向图，应用Dijkstra算法计算从源顶点1到其它顶点间最短路径。010∞

30

100∞

050∞

∞∞∞0∞10∞

∞20060∞

∞

∞∞0用邻接矩阵表示如右图：Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientPro.Copyright2004-2011AsposePtyLtd.19Dijkstra算法的选择策略开始时集合S中只有一个点，即源用dist[i]存储源点到顶点i的距离Dijkstra算法每次从S外选取距离源点最近的顶点u，添加到S中，同时修改源点到S外的点最短距离dist数组。一旦S包含了所有V中顶点，dist就记录了从源到所有其它顶点之间的最短路径长度。Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientPro.Copyright2004-2011AsposePtyLtd.208.3单源最短路径迭代Sudist[2]dist[3]dist[4]dist[5]初始{1}-10maxint301001{1,2}21060301002{1,2,4}4105030903{1,2,4,3}3105030604{1,2,4,3,5}510503060Dijkstra算法的迭代过程：

Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientPro.Copyright2004-2011AsposePtyLtd.21

初始状态下，S中只有一个点（源点v1）。-11-111010∞3010010000s:dist:path:①S[i]为顶点i是否属于集合Sdist[i]为源到顶点i的最短特殊路径长度path[i]为顶点i的最优前驱顶点Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientPro.Copyright2004-2011AsposePtyLtd.22

第二步，将S外距离S最近的点v2加入S。更新相应信息。-11-111010∞3010010000s:dist:path:1①②602Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientPro.Copyright2004-2011AsposePtyLtd.23

第三步，将S外距离S最近的点v4加入S。更新相应信息。-11211010603010011000s:dist:path:1①②504④904Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientPro.Copyright2004-2011AsposePtyLtd.24

第四步，将S外距离S最近的点v3加入S。更新相应信息。-1141401050309011010s:dist:path:1①②603④③Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientPro.Copyright2004-2011AsposePtyLtd.25

第五步，将S外距离S最近的点v5加入S。更新相应信息。-1141301050306011110s:dist:path:1①②④③⑤Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientPro.Copyright2004-2011AsposePtyLtd.26voidDijkstra(intG[][N],intv0,intdist[],intpath[]，intn)//源点v0到其他顶点的最短距离dist和最短路径下标path{int*s=newint［n］;intminDis,i,j,u;

//初始化三个数组

Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientPro.Copyright2004-2011AsposePtyLtd.27//逐次将各点加入S//在当前还未找到最短路径的顶点集中选取具有最短距离的顶点u//标记顶点u已从集合T加入到集合S中//修改从v0到其他顶点的最短距离和最短路径Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientPro.Copyright2004-2011AsposePtyLtd.28voidDijkstra(intG[][N],intv0,intdist[],intpath[]，intn)//从源点v0到其他顶点的最短距离dist和最短路径下标path{int*s=newint［n］;intminDis,i,j,u;

//初始化三个数组for(i=0;i<n;i++){Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientPro.Copyright2004-2011AsposePtyLtd.29dist［i］=G[v0][i];s［i］=0;if(I!=v0&&dist［i］<MAX)path［i］=v0;elsepath［i］=-1;}s［v0］=1;//标记顶点v0已从集合T加入到集合S中//在当前还未找到最短路径的顶点集中选取具有最短距离的顶点ufor(i=1;i<n;i++){minDis=MAX;for(j=0;j<=n;j++)Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientPro.Copyright2004-20