粗略理解floyd算法的原理

为了加深对floyd算法的认识，特地搜了一下floyd算法的证明。原来floyd算法的本质是一个动态规划的过程。

状态转移方程：

f[k][i][j]=min(f[k-1][i][j],f[k-1][i][k]+f[k-1][k][j])

f[k][i][j]表示只经过前k个点(包括k)，从i到j的最小值。当k从1到n时，就是从i到j的最小值。我们熟悉的用二维数组的写法实际上是对空间的一种压缩。

解释一下：

计算只经过前k个点，从i到j的最小值时，有两种情况需要考虑：经过第k个点和不经过第k个点。经过第k个点则距离应是从i到k的最小值和从k到j的最小值，两个最小值的路径都必须只经过前k-1个点（为什么是k-1而不是k，事实上他们两数值相同，因为起点和终点已经有第k个点，只是在dp的过程中先产生k-1，f[k][i][k]和f[k][k][j]有可能比f[k][i][j]的值晚计算出，就不能在计算f[k][i][j]时用到这两个值）。不经过k的点则距离与只经过前k-1个点时一样。

下面是一个试验的代码：

[cpp] view plaincopy

1. #include<iostream>  
2. #include<cstring>  
3. #include<cstdio>  
4. using namespace std;  
5.   
6. const int INF=1<<28;  
7. const int MAXN=50;  
8. int n;  
9. int g[MAXN][MAXN],f[MAXN][MAXN][MAXN];  
10.   
11. void floyd();  
12. void floyd2();  
13.   
14. int main()  
15. {  
16.     freopen("in.txt","r",stdin);  
17.     cin>>n;  
18.     for(int i=0;i<=n;i++)  
19.         for(int j=0;j<=n;j++)  
20.             g[i][j]=INF;  
21.     for(int k=0;k<=n;k++)  
22.         for(int i=0;i<=n;i++)  
23.             for(int j=0;j<=n;j++)  
24.                 f[k][i][j]=INF;  
25.   
26.     for(int i=1;i<=n;i++)  
27.         for(int j=1;j<=n;j++)  
28.         {  
29.             cin>>g[i][j];  
30.             f[0][i][j]=g[i][j];  
31.         }  
32.     floyd();  
33.     floyd2();  
34.     for(int i=1;i<=n;i++)  
35.         for(int j=1;j<=n;j++)  
36.             if(g[i][j] != f[n][i][j])  
37.             {  
38.                 printf("difference at [%d][%d] while g=%d but f=%d\n",  
39.                        i,j,g[i][j],f[n][i][j]);  
40.             }  
41.   
42.     return 0;  
43. }  
44.   
45. void floyd()  
46. {  
47.     for(int k=1;k<=n;k++)  
48.         for(int i=1;i<=n;i++)  
49.             for(int j=1;j<=n;j++)  
50.                 if(g[i][j]>g[i][k]+g[k][j])  
51.                     g[i][j]=g[i][k]+g[k][j];  
52. }  
53.   
54. void floyd2()  
55. {  
56.     for(int k=1;k<=n;k++)  
57.         for(int i=1;i<=n;i++)  
58.             for(int j=1;j<=n;j++)  
59.                 f[k][i][j]=min(f[k-1][i][j],f[k-1][i][k]+f[k-1][k][j]);  
60. }  
61.   
62. /* 
63. 10 
64. 1 2 3 4 1 1 2 3 4 5 
65. 3 2 1 5 9 6 5 8 9 1 
66. 1 2 3 6 5 9 7 4 2 9 
67. 4 2 5 3 2 1 4 2 9 8 
68. 1 2 3 4 5 3 8 2 1 3 
69. 1 2 3 4 1 2 2 3 4 2 
70. 3 2 1 5 9 2 1 3 4 2 
71. 1 2 3 6 5 1 3 2 1 2 
72. 4 2 5 3 2 3 4 2 4 6 
73. 1 2 3 4 5 5 3 2 4 5 
74. */