前言

经过一个假期的集训，Payphone-X发现自己太菜了。他想要变强！于是乎，他开始学习最短路。

引入

在开始最短路的学习之前，我们不妨看一道题目

khGAf0.jpg

暑假，小哼准备去一些城市旅游。

在他旅行之前，他提前查了一下地图，发现有些城市之间有公路，有些城市之间则没有，城市之间的公路长度也不一样。

地图如下

khG3fx.png

为了节省经费以及方便计划，小哼希望在出发之前知道任意两个城市之间的最短路程。

聪明的你，能帮帮可爱的小哼吗？

（ps.最短路的所有题目不遵循三角不等式，so不要讽刺作者的数学了）

算法分析

看完地图之后，是不是有了点想法。

是不是觉得对每两个点跑dfs一遍就行了？

嗯……

你会TLE到飞起

所以，还有别的办法吗？

想一想……

如果我们想让两个点的路径更短，是不是可以尝试一下引入第三个点？

就像下图

khJlDg.png

如果我们从A到C，再从 C到B，是不是比直接从A到B的距离更短。

这，就是Floyd算法的核心。

Floyd的算法实现

Floyd算法的强大之处在于它是四大最短路算法中唯一一个求多元最短路的算法

额……

好像忘了科普多元最短路了。

最短路算法分为单元最短路与多元最短路

单元最短路指从一个点到除它以外所有点的最短路，而多元最短路指从每个点到除它以外所有点的最短路

而Floyd是唯一一个求多元最短路的算法。

并且Floyd算法实现难度很低，只有3个循环与一个if语句。

代码如下

for(int k =  1; k <= n; k++){   //枚举中间的城市
    for(int i = 1; i <= n; i++){    //枚举起点城市
        for(int j = 1; j <= n; j++){    //枚举终点城市
            if(w[i][j] > w[i][k] + w[k][j]){    //w[i][j]表示从i到j的最短路
                w[i][j] = w[i][k] + w[k][j];
            }
        }
    }
}

当然，Floyd也可以用来判断两个点是否连通，只需要稍加修改一下if之中的语句即可。

时间复杂度为

附件(Floyd模板)

#include<iostream>
using namespace std;
int n;
int a, b,chang;
int w[1000][1000];
int main(){
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a >> b >> chang;
         w[a][b] = chang;
    } 
    for(int k = 1; k <= n; k++){
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                if(w[i][j] > w[i][k] + w[k][j]){
                    w[i][j] = w[i][k] + w[k][j];
                }
            }
        }
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            cout << w[i][j] <<endl;
        }
    }
    return 0;
}

THE END