最短路问题——Floyd算法详解（附模板、解析注释）

· · 个人记录

Floyd算法

中文名：弗洛伊德算法

又名：插点法

原理部分

Floyd算法中含有 贪心、 动态规划的思想

Floyd算法通过枚举所有 “中转点”，判断 起点经此中转点到达终点是否比 起点直接到达终点所需代价少，故名 “插点法”。

数据部分

Floyd算法共有 3层循环， 从外到内分别枚举 中转点->起点->终点。每次枚举数目为n，故时间复杂度为O(n³)。

优缺点

Floyd的优点在于代码简单易懂，代码量极少。并且支持负权。

Floyd适用性广，因独特的算法特性做一次就能将所有起点、终点的情况求出。

缺点在于效率远低于同类其他算法，如 Dijkstra、Bellman-Ford、SPFA (正经文章，先不提内啥了，dddd) 等。还有就是不支持负环(负权回路）。

模板部分（附解析注释）

void Floyd() {
    for (int k = 0; k < n; k++) {   //k为“中转点”，中转点在最外层循环！
        for (int i = 0; i < n; i++) {   //i为起点
            for (int j = 0; j < n; j++) {   //j为终点
                a[i][j] = min(a[i][j], a[i][k] + a[k][j]);  //取经过中转点与不经过中转点的最小值
            }
        }
    }
}