floyd最短路径算法

floyd 算法是基于DP（动态规划的一种算法），用于求每对顶点之间的最短路。

floyd 算法是 三层 for 循环 ，复杂度是O(v^3) ,并且 隐藏在 O（v^3）下的常数也是非常小

算法介绍：

• 它需要用邻接矩阵来储存边
  
• 从任意一条单边路径开始。所有两点之间的距离是边的权，如果两点之间没有边相连，边权就是无穷大。
• 对于每一对顶点 u 和 v，看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比己知的路径更短。如果是更新它。这种方法做松弛技术。松弛技术是三角关系     实质就是 ：   d(s,u)= min(d(s,u), d(s,v)+d(v,u) )   。d(s,u)  表示从s点到 u 点的路径长度。。。也就是如果找到一条比当前路径更短的路径长度，就更新当前的路径长度。。

这个算法通过考虑最佳子路径来得到最佳路径。这个算法很容易实现，只要几行。

 dp状态转移的方程是 ：   dp[k,i,j]=min(dp[k-1,i,j],dp[k-1,i,k]+dp[k-1,k,j])

[html] view plaincopy

1. for(int k =1 ;  k <= n ; k ++ ){  
2.   
3.     for(int i =1 ; i<= n ; i++){  
4.   
5.         for(int j =1 ;j<=n;j++){  
6.   
7.                dp[k][ i ][ j ]= min( dp[k-1][ i ][ j ],dp[k-1][ i ][ k ]+dp[k-1][ k ][ j ] );        
8.   
9.           }  
10.   
11.      }  
12.   
13. }