每对顶点间的最短路径之一 收藏

这里给出的是基于动态规划方法，时间复杂度时O(v^4)，可以通过“重复平方”计数使其复杂度降低位O(v^3*lgv).参考《算法导论》25.1

view plaincopy to clipboardprint?
#include <iostream>
using namespace std;
const int N = 5;
const int E = 9;
const int MAX=0xffff;
int g[N][N];
/*
* 这里l1代表“最多包含m-1条边的最短路径矩阵”
* l2作为返回值，代表最多包含m条边的最短路径矩阵。
* 其中l2(i,j) = min {l1(i,j), min {l1(i,k)+g[k][j]}};其中0<=k<=N-1
*/
int ** extend_shortest_path(int **l1)
{
int n = N;
int i=0,j=0;
int ** l2 = new int*[N];
for(i=0;i<n;i++)
l2[i] = new int[N];
int k = 0;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
l2[i][j] = MAX;
for(k=0;k<n;k++)
{
int t1 = l2[i][j];
int t2 = l1[i][k] + g[k][j];
if(t1 < t2)
l2[i][j] = t1;
else
l2[i][j] = t2;
}
}
return l2;
}
/*
* 每次迭代由L(m-1)求出L(m),即延伸一条边
* 初始化L1=G=(g[i][j])
* 其中m=0时，如果i==j，l0(i,j) =0;如果i!=j，l0(i,j)=MAX
* 故只需要从m＝1开始考虑
*/
int ** slow_all_pairs_shortest_path()
{
int i = 0;
int j = 0;
int ** l1 = new int *[N];
for(i=0;i<N;i++)
l1[i] = new int[N];
for(i=0;i<N;i++)
for(j=0;j<N;j++)
l1[i][j] = g[i][j];
int ** l2;
int m = 2;
for(m=2;m<=N-1;m++)
{
l2 = extend_shortest_path(l1);
for(i=0;i<N;i++)
delete []l1[i];
delete []l1;
l1 = l2;
}
return l1;
}
int main()
{
int i = 0,j=0;
for(i=0;i<N;i++)
for(j=0;j<N;j++)
if(i==j)
g[i][j] = 0;
else
g[i][j] = MAX;
int c = 0;
while(c<E)
{
cin>>i;
cin>>j;
cin>>g[i][j];
c++;
}
int ** l = slow_all_pairs_shortest_path();
for(i=0;i<N;i++)
{
for(j=0;j<N;j++)
cout << l[i][j] << " ";
cout << endl;
}
}

本文来自CSDN博客，转载请标明出处：http://blog.csdn.net/clearriver/archive/2009/09/13/4547831.aspx