floyd算法

floyd算法复杂度是o(n^3)；n为节点数

思想是dp思想，类似区间dp；

f[i][j]表示节点i到节点j的最短路径和；

1.i-j可以由i直接到j

2.i-j可以经过中间节点i-k-j来更新，k相当于节点集，用换元的视角去看k;

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 dp[i][j]=min(dp[i][k]+dp[k][j]);

代码我们更新中间节点是从小到大更新的；

假设1-10的一条最短路径为 1-9-2-4-10;

到k=9的时候我们就能更新出1-10的最短路径，因为2，4两个节点会在前面作为中间节点更新掉。