Floyd算法求最短路径

Floyd算法

这是一个代码非常简洁的求最短路径算法，让人不禁感叹：“这就完啦？”

弗洛伊德（Floyd）算法求图的最短路径_弗洛伊德算法求最短路径-CSDN博客
Floyd算法以中介点（我更喜欢叫它中间点，因为这个中间点和作为判断对象的另外两个点不一定直接相连）为切入口 遍历所有可能的路径 不断取最小路径

快速使用：

1
2
3
4

for (int k = 0; k < n; ++k)
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

Floyd算法为什么不会漏？↓

补充：对于v4->v7最短路径=v4->v6->v3->v7
如果调换v3和v6位置 当k=6时 还会判断一次v4->v7的最短路径 并不是挨着的顶点才更新 三层循环会遍历所有的情况
floyd算法:我们真的明白floyd吗?_佛罗伊德算法为什么可以求出最短路径-CSDN博客

总结

Floyd算法用k表示中间点编号
用i和j遍历整个表来更新最短路径
Floyd算法始终在求解一个问题：

|—-|
|如果我从i到j的途中经过k 这条路会更短吗？|