hihocoder1089 Floyd算法

浏览数：23 / 时间：2015年06月08日

题目链接：http://hihocoder.com/problemset/problem/1089

算法描述：

floyd算法是求解图中任意两点最短路的经典算法，复杂度为O(n^3)。虽然我们完全可以用n次dijkstra算法来求任意两点的最短路，复杂度也是O(N^3)，但如果有一个算法只需要5行代码就可以完成我们想做的事情，我们有什么理由不用它？！

floyd算法主要用了动态规划的思想：

设d[i][j]表示i到j的最短路径的长度, 那么我们可以这样来求解d[i][j]:

（1）首先，i到j的路径只允许经过节点1，那么：d[i][j] = min(d[i][j], d[i][1]+d[1][j]);

（2）然后我们逐步放开限制，i到j的路径只允许经过点1,2, 那么在（1）的基础上继续更新d[i][j]的值有：d[i][j] = min(d[i][j], d[i][2]+d[2][j]);

.......

注意逐步放开限制的过程！

写成代码就5行：

1 for(int k=1; k<=n; ++k)
2     for(int i=1; i<=n; ++i)
3         for(int j=1; j<=n; ++j)
4             if(i!=j&&j!=k&&d[i][k]!=INF&&d[k][j]!=INF)
5                 d[i][j] = min(d[i][j], d[i][k]+d[k][j]);

我的完整代码：

 1 #include <iostream>
 2 
 3 using namespace std;
 4 
 5 #define MAXN 105
 6 #define INF 0x7fffffff
 7 
 8 int d[MAXN][MAXN], n, m;
 9 
10 void init()
11 {
12     for(int i=1; i<=n; ++i) d[i][i] = 0;
13     for(int i=1; i<=n; ++i) for(int j=1; j<=n; ++j) if(i!=j) d[i][j] = INF;
14 }
15 
16 void floyd()
17 {
18     for(int k=1; k<=n; ++k)
19         for(int i=1; i<=n; ++i)
20             for(int j=1; j<=n; ++j)
21                 if(i!=j&&j!=k&&d[i][k]!=INF&&d[k][j]!=INF)
22                     d[i][j] = min(d[i][j], d[i][k]+d[k][j]);
23 }
24 
25 int main()
26 {
27     while(cin>>n>>m)
28     {
29         init();
30         while(m--)
31         {
32             int u, v, w;
33             cin>>u>>v>>w;
34             d[u][v] = d[v][u] = min(w, d[u][v]);
35         }
36         floyd();
37         for(int i=1; i<=n; ++i)
38         {
39             for(int j=1; j<n; ++j) cout<<d[i][j]<<" ";
40             cout<<d[i][n]<<endl;
41         }
42     }
43     return 0;
44 }