面对现实,超越自己
逆水行舟,不进则退
posts - 269,comments - 32,trackbacks - 0

Floyd-Warshall算法,简称Floyd算法,用于求解任意两点间的最短距离,时间复杂度为O(n^3)。

使用条件&范围
通常可以在任何图中使用,包括有向图、带负权边的图。

Floyd-Warshall 算法用来找出每对点之间的最短距离。它需要用邻接矩阵来储存边,这个算法通过考虑最佳子路径来得到最佳路径。

1.注意单独一条边的路径也不一定是最佳路径。
2.从任意一条单边路径开始。所有两点之间的距离是边的权,或者无穷大,如果两点之间没有边相连。
对于每一对顶点 u 和 v,看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比己知的路径更短。如果是更新它。
3.不可思议的是,只要按排适当,就能得到结果。
伪代码:

 1 // dist(i,j) 为从节点i到节点j的最短距离
 2 For i←1 to n do
 3    For j←1 to n do
 4       dist(i,j) = weight(i,j) 
 5  
 6 For k←1 to n do // k为“媒介节点”
 7    For i←1 to n do
 8       For j←1 to n do
 9          if (dist(i,k) + dist(k,j) < dist(i,j)) then // 是否是更短的路径?
10             dist(i,j) = dist(i,k) + dist(k,j)

我们平时所见的Floyd算法的一般形式如下:

 

1 void Floyd(){
2      int i,j,k;
3      for(k=1;k<=n;k++)
4          for(i=1;i<=n;i++)
5              for(j=1;j<=n;j++)
6                  if(dist[i][k]+dist[k][j]<dist[i][j])
7                      dist[i][j]=dist[i][k]+dist[k][j];
8 }

注意下第6行这个地方,如果dist[i][k]或者dist[k][j]不存在,程序中用一个很大的数代替。最好写成if(dist[i] [k]!=INF && dist[k][j]!=INF && dist[i][k]+dist[k][j]

Floyd算法的实现以及输出最短路径和最短路径长度,具体过程请看【动画演示Floyd算法】。

代码说明几点:

1、A[][]数组初始化为各顶点间的原本距离,最后存储各顶点间的最短距离。

2、path[][]数组保存最短路径,与当前迭代的次数有关。初始化都为-1,表示没有中间顶点。在求A[i][j]过程中,path[i][j]存放从顶点vi到顶点vj的中间顶点编号不大于k的最短路径上前一个结点的编号。在算法结束时,由二维数组path的值回溯,可以得到从顶点vi到顶点vj的最短路径。

初始化A[][]数组为如下,即有向图的邻接矩阵。



完整的实现代码如下:

  1 #include <iostream>
  2 #include <string>   
  3 #include <stdio.h>   
  4 using namespace std;   
  5 #define MaxVertexNum 100   
  6 #define INF 32767   
  7 typedef struct  
  8 {   
  9     char vertex[MaxVertexNum];   
 10     int edges[MaxVertexNum][MaxVertexNum];   
 11     int n,e;   
 12 }MGraph;   
 13  
 14 void CreateMGraph(MGraph &G)   
 15 {   
 16     int i,j,k,p;   
 17     cout<<"请输入顶点数和边数:";   
 18     cin>>G.n>>G.e;   
 19     cout<<"请输入顶点元素:";   
 20     for (i=0;i<G.n;i++)   
 21     {   
 22         cin>>G.vertex[i];   
 23     }   
 24     for (i=0;i<G.n;i++)   
 25     {   
 26         for (j=0;j<G.n;j++)   
 27         {   
 28             G.edges[i][j]=INF;   
 29             if (i==j)   
 30             {   
 31                 G.edges[i][j]=0;   
 32             }   
 33         }   
 34     }      
 35     for (k=0;k<G.e;k++)   
 36     {   
 37         cout<<"请输入第"<<k+1<<"条弧头弧尾序号和相应的权值:";   
 38         cin>>i>>j>>p;   
 39         G.edges[i][j]=p;   
 40     }   
 41 }   
 42 void Dispath(int A[][MaxVertexNum],int path[][MaxVertexNum],int n);
 43  
 44 void Floyd(MGraph G)
 45 {
 46     int A[MaxVertexNum][MaxVertexNum],path[MaxVertexNum][MaxVertexNum];
 47     int i,j,k;
 48     for (i=0;i<G.n;i++)
 49     {
 50         for (j=0;j<G.n;j++)
 51         {
 52             A[i][j]=G.edges[i][j];
 53             path[i][j]=-1;
 54         }
 55     }
 56     for (k=0;k<G.n;k++)
 57     {
 58         for (i=0;i<G.n;i++)
 59         {
 60             for (j=0;j<G.n;j++)
 61             {
 62                 if (A[i][j]>A[i][k]+A[k][j])
 63                 {
 64                     A[i][j]=A[i][k]+A[k][j];
 65                     path[i][j]=k;
 66                 }
 67             }
 68         }
 69     }
 70     Dispath(A,path,G.n);
 71 }
 72  
 73 void Ppath(int path[][MaxVertexNum],int i,int j)
 74 {
 75     int k;
 76     k=path[i][j];
 77     if (k==-1)
 78     {
 79         return;
 80     }
 81     Ppath(path,i,k);
 82     printf("%d,",k);
 83     Ppath(path,k,j);
 84 }
 85  
 86 void Dispath(int A[][MaxVertexNum],int path[][MaxVertexNum],int n)
 87 {
 88     int i,j;
 89     for (i=0;i<n;i++)
 90     {
 91         for (j=0;j<n;j++)
 92         {
 93             if (A[i][j]==INF)
 94             {
 95                 if (i!=j)
 96                 {
 97                     printf("从%d到%d没有路径\n",i,j);
 98                 }
 99             }
100             else
101             {
102                 printf("  从%d到%d=>路径长度:%d路径:",i,j,A[i][j]);
103                 printf("%d,",i);
104                 Ppath(path,i,j);
105                 printf("%d\n",j);
106             }
107         }
108     }
109 }
110  
111 int main()
112 {
113     freopen("input2.txt""r", stdin);
114     MGraph G;
115     CreateMGraph(G);
116     Floyd(G);
117     return 0;
118 }

测试结果如下:



本文转自:http://www.wutianqi.com/?p=1903

posted on 2012-06-30 16:18 王海光 阅读(8867) 评论(2)  编辑 收藏 引用 所属分类: 算法

FeedBack:
# re: 最短路径算法—Floyd(弗洛伊德)算法分析与实现(C/C++)
2015-08-04 17:13 | 11111111
为什么不能运行
  回复  更多评论
  
# re: 最短路径算法—Floyd(弗洛伊德)算法分析与实现(C/C++)
2015-12-25 11:15 | 大神
没有error,没有warning,但是点运行后提示Cannot execute pragram。怎么回事阿  回复  更多评论
  

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理