【问题】：设G=（V,E）是一个有向图，其中的每条边（i,j）有一个非负长度L[i][j]，如果从顶点i到顶点j没有边，则L[i][j]=0，这里我们要解决问题就是：找出从每个顶点到其他所有顶点的距离D[i][j]
【解题】：这里我们要用动态划分算法来解决这个问题：用自底向上的递推式方法来处理。先将L[i][j]中的值全部复制到D[i][j]中，然后通过3重for循环对D[N][N]进行N-1次迭代。保证D[i][j]为最小值。该算法的时间复杂度:o(n3),空间复杂度:o(n2);这就是floyd求最短路径的算法
【程序】：代码如下
#include<iostream.h>
#define N 6
int l[N][N],D[N][N];
void floyd()
{
int i,j,k;
for(i=1;i<N;i++)
for(j=1;j<N;j++)
D[i][j]=l[i][j];
for(k=1;k<N;k++)
for(i=1;i<N;i++)
for(j=1;j<N;j++)
{
int m;
if(i!=j && D[i][k]!=0 && D[k][j]!=0)
{
m=D[i][k]+D[k][j];
if(D[i][j]==0)
D[i][j]=m;
else if(m<D[i][j])
D[i][j]=m;
}
}
}
void main()
{
for(int i=1;i<N;i++)
{ for(int j=1;j<N;j++)
cin>>l[i][j];
}
cout<<endl;
floyd();
for(i=1;i<N;i++)
{ for(int j=1;j<N;j++)
cout<<D[i][j]<<" ";
cout<<endl;
}
}