多源最短路径floyd算法

时间:2022-11-25 20:14:58

多源最短路径floyd算法

其实相当简单。
基本思想就是一个贪心法,构造1个二维矩阵进行迭代,时间复杂度为o(n^3)。
二维数组g[][]表示图上边的权(就是2个点之间的直接距离)
二维数组weight[][]是我们构造出来的二维矩阵,用来储存当前得到的最短路径。
首先,用g[][]来初始化weight[][](把g里的数据copy到weight里)
接下来,遍历图中所有结点v
如果g[i][v]+g[v][j]<weight[i][j]
那么weight[i][j]=g[i][v]+g[v][j]
遍历完所有结点之后,weight里储存的就是每两个点之间的最短路径
证明过程就不写了,几乎每本算法书里都有的,而且我觉得也没什么必要


下面是c的实现
g[i][j]=0表示 i 到 j 无路径
void floyd(float **g,long n,float **weight)
{
        long i,j,k;
        for(i=0;i<n;i++)
                for(j=0;j<n;j++)
                        weight[i][j]=g[i][j];
        for(k=0;k<n;k++)
         for(i=0;i<n;i++)
         {
                 if(g[i][k]==0)
                         continue;
                  for(j=0;j<n;j++)       
                  {
                          if(g[k][j]==0)
                                  continue;
                          if(weight[i][j]==0 ||
                                  g[i][k]+g[k][j]<weight[i][j])
                                  weight[i][j]=g[i][k]+g[k][j];
                  }
         }
}

 

 


 floyd算法
#include "iostream.h"
int min(int a,int b)
{
 return a>b?b:a;
}
int cost[10][10]=
{
 0,    99,      8,     7,     6,     5,    4,     3,     2,     1, 
 99,    0,     99,     8,     7,     6,    5,     4,     3,     2,
 8,    99,      0,    99,     8,     7,    6,     5,     4,     3,
 7,     8,     99,     0,    99,     8,    7,     6,     5,     4,
 6,     7,      8,    99,     0,    99,    8,     7,     6,     5,
 5,     6,      7,     8,    99,     0,   99,     8,     7,     6,
 4,     5,      6,     7,     8,    99,    0,    99,     8,     7,
 3,     4,      5,     6,     7,     8,   99,     0,    99,     8,
 2,     3,      4,     5,     6,     7,    8,    99,     0,    99,
 1,     2,      3,     4,     5,     6,    7,     8,     99,    0
};
int best[10][10];

void Floyd(int cost[10][10],int best[10][10])
{
 int i,j,k;
 for(i=0;i<10;i++)
 for(j=0;j<10;j++)
  best[i][j]=cost[i][j];
 for(i=0;i<10;i++)
 for(j=0;j<10;j++)
 for(k=0;j<10;j++)
 {
  best[j][k]=min(best[j][k],best[i][j]+best[i][k]);
 }
}

main()
{
 Floyd(cost,best);
 for(int i=0;i<10;i++)
 {
  for(int j=0;j<10;j++)
  cout<<best[i][j]<<" ";
  cout<<endl;
 }
}
 ------------------------------------------------------------------------------------------------------------------------------------------

 每对顶点间的最短路径——弗洛伊德(Floyd)算法
    解决此问题有两种方法:其一是分别以图中每个顶点为源点共调用n次Dijkstra算法;其二是采用Floyd算法。两种算法的时间复杂度均为O(n3),但后者形式上比较简单。
    Floyd算法的基本思想:
    (1)利用二维数组A[1..n-1][1..n-1], A[i][j]记录当前vi到vj的最短路径长度,数组A的初值等于图的代权临街矩阵;
    (2)集合S记录当前允许的中间顶点,初值S=Φ;
    (3)依次向S中加入v0 ,v1… vn-1,每加入一个顶点,对A[i][j]进行一次修正:设S={v0 ,v1… vk-1},加入vk,则A(k)[i][j] = min{ A(k-1)[i][j],A(k-1)[i][k]+A(k-1)[k][j]}。
A(k)[i][j]的含义:允许中间顶点的序号最大为k时从vi到vj的最短路径长度。
    A(n-1)[i][j]就是vi到vj的最短路径长度。

本文来自CSDN博客,转载请标明出处:http://blog.csdn.net/zhoujunyi/archive/2007/09/29/1806343.aspx