图任意两点最短距离.ppt

《图任意两点最短距离.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、图的任意两点间的距离问题的描述：已知图G=(V,E),V={v1,v2,…,vn}及距离矩阵D=（dij)nn求图G的任意两点间的最短距离。分析：图的问题有25个，这个问题的算法是Floyd提出的。设矩阵，定义矩阵运算如下：其中令显然表示从出发经过某一中间点到达点的最短距离。同样表示从经过两个中间点到的最短距离。定义：令则表示从vi点到vj点的最短距离。由于D(k)有n2个元素，每个元素要作n-2次加法与n-3次比较，依以上办法可知求的时间复杂性为。动态规划算法设为从vi出发中途经过以(v1,v2,…,vk)为中间点到vj的最短距离。则有其中并且即为

2、i,j之间的最短距离。具体算法voidSD(intd[][],intn){inta[n][n],I,j,k;for(i=1;i<=n;i++)for(j=1;j<=n;j++)a[i][j]=d[i][j];for(k=1;k<=n;k++)for(i=1;i<=n;i++)for(j=1;j<=n;j++)if(a[i][j]>a[i][k]+a[k][j])a[i][j]=a[i][k]+a[k][j]for(i=1;i<=n;i++){for(j=1;j<=n;j++)printf(“%d“,a[i][j];printf(“”);}}举例见

3、材料0-1背包问题给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?0-1背包问题是一个特殊的整数规划问题。0-1背包问题设所给0-1背包问题的子问题的最优值为m(i，j)，即m(i，j)是背包容量为j，可选择物品为i，i+1，…，n时0-1背包问题的最优值。由0-1背包问题的最优子结构性质，可以建立计算m(i，j)的递归式如下。算法复杂度分析：从m(i，j)的递归式容易看出，算法需要O(nc)计算时间。当背包容量c很大时，算法需要的计算时间较多。例如，当c>2n时，算

4、法需要Ω(n2n)计算时间。