最短路径之Floyd算法

学习数据结构与算法
2021-05-17 14:29 · 阅读时长4分钟

Floyd算法是一种求多源最短路径的算法,并且支持有负权的图,但不可以存在负权回路,它是一种动态规划算法,时间复杂度是O(V3),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算法求最短路径的过程如下

加载中...

代码实现如下

加载中...
Floyd最短路径