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

7.5所有点对的最短路径问题 对于一个各边权值均大于0的有n个顶点的带权有向图G=(V,E)，求所有顶点之间的最短路径和最短距离。 复习Dijkstra算法 其基本思想是，设置顶点集合S并不断地作贪心选择来扩充这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。 初始时，S中仅含有源点。设u是G的某一个顶点，把从源点到u且中间只经过S中顶点的路称为从源到u的特殊路径，并用数组distance记录当前每个顶点所对应的最短特殊路径长度。Dijkstra算法每次从V-S中取出具有最短特殊路长度的顶点u，将u添加到S中，同时对数组distance作必要的修改。一旦S包含了所有V中顶点，distance就记录了从源到所有其它顶点之间的最短路径长度。 算法中，我们不断更新以下三个数组： s数组: s[i]，当顶点i加入S时，s[i]置1 Distance数组: Distance[i]记录原点到 顶点i的最短特殊路径长度。 path数组： path[i]记录顶点i在其最短特殊路径上的前驱顶点。由该数组可求得原点到各点的最短路径。如：设源点是顶点1, path数组如下 例如，对右图中的有向图，应用Dijkstra算法计算从源顶点1到其它顶点间最短路径的过程列在下页的表中。 方法一：重复调用Dijkstra算法n次 可轮流以每一个顶点为源点，重复调用狄克斯特拉算法函数Dijkstra() n次，即可求得所有顶点之间的最短路径和最短距离。 利用Dijkstra()函数求所有顶点之间的最短路径算法如下。其中，distance[i][j]中存放着从顶点i到顶点j的最短距离，path[i][j]中存放着从顶点i到顶点j的最短路径的前一顶点下标。 voidShortPath(AdjMWGraph G, int **distance, int **path) { Int n=G.NumOfVertices(); for(inti=0;in;i++) Dijkstra(G,i,distance［i］,path［i］); } 该问题具有最优子结构性质 例如上图中，若路线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=L[i][j] (因为从i到j不允许经过任何其他顶点） 若1≤k ≤ n, di,jk=min{di,jk-1 , di,kk-1 +dk,jk-1} 计算过程 例：考虑下图所示的带权有向图，求所有顶点之间的最短距离。 算法设计 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++) D[i*n+j]=min(D[i*n+j], D[i*n+k]+D[k*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到其它顶点间最短路径。 Dijks