yuanyuelang

常用链接

统计

最新评论

每对顶点间的最短路径之Floyd-Warshall算法

        Floyd-Warshall算法的基本思路是：
   1.用D[v][w]记录每对顶点间的最短距离
   2.对每一个图中的顶点，以其作为基点扫描每一对D[v][w]，检验是否通过该基点可以使得这对顶点间的距离变小。

我们实际是很容易就可以写出这个算法的代码：
#define N 100
void Floyd(int dist[N][N],int n)
{
  int i,j,k;
  for(k=0;k<n;k++)
    for(i=0;i<n;i++)
      for(j=0;j<n;j++)
        if(dist[i][k]+dist[k][j]<dist[i][j])
           dist[i][j]=dist[i][k]+dist[k][j];
        
}
  

我们还面临一个保存路径的问题,如何来做呢？
#define N 100
int map[N][N];
void Floyd(int dist[N][N],int path[N][N],int n)
{
  int i,j,k;
  for(i=0;i<n;i++)
    for(j=0;j<n;j++)
      dist[i][j]=map[i][j],path[i][j]=0;
  for(k=0;k<n;k++)
    for(i=0;i<n;i++)
      for(j=0;j<n;j++)
        if(dist[i][k]+dist[k][j]<dist[i][j]){
           dist[i][j]=dist[i][k]+dist[k][j];
           path[i][j]=k;
        
}

void output(int i,int j)
{
  if(i==j) return;
  if(path[i][j]==0) cout<<j<<" ";
  else{
    output(i,path[i][j]);
    output(path[i][j],j);
  }
}
  

posted on 2009-09-23 11:35 原语饿狼 阅读(345) 评论(0)  编辑 收藏 引用 所属分类: 图论


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理