最短路--Floyd

Floyd是用来求全局任意两点之间的最短路的。

Floyd很好理解,依次用每个点去松弛其它所有边,感觉没什么好讲的。理解了dijkstraSPFA之后,感觉Floyd就很简单易懂了,直接上代码吧。

时间复杂度:O(n^3)

空间复杂度:O(n^2)

算法实现

1
2
3
4
for(int k=0; k<n; k++)//1.
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
d[i][j] = min(d[i][j], d[i][k]+d[k][j]);

注释:

  1. 其中n为图中顶点个数,k依次枚举所有顶点去松弛其它所有边。
Donate comment here