最短路径之Floyd算法

Floyd算法是一种求多源最短路径的算法，并且支持有负权的图，但不可以存在负权回路，它是一种动态规划算法，时间复杂度是O(V³)，V是顶点的个数。

主要思路是，对于任意两个顶点i和顶点j，距离为d[i][j]，我们遍历所有顶点，如果发现某个顶点k满足d[i][j]>d[i][k]+d[k][j]则更新d[i][j]为d[i][k]+d[k][j]，当所有顶点都遍历完成后，就得到任意两个顶点之间的最短路径。

比如下面这个图，使用Floyd算法求最短路径的过程如下

代码实现如下