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
王海光 阅读(11245)
评论(2) 编辑 收藏 引用 所属分类:
算法