图结构_最短路_Floyd算法模板

适用范围：求一个边有权值的有向联通图，求点i，到点j的最短路或最长路

复杂度：空间复杂度n^2,时间复杂度o（n^3）

算法概述：

我如果要从点i到点j那么我可以选择以下几种方式

从i直接到j

从i，经过点1，然后到j

从i，经过点2，然后到j

.........

Floyd算法就是遍历中间经过的点并取最值

他可能经过点1，点1，3 ，4，很多种情况先记住这东西，看后面的代码室就会知道我是怎么用o（n^3）来解决这个问题的

初始化：直接输入这个图和边即可，从点i，到点j的边的权值用map[i][j]表示即可

代码模板：

void Floyd(int n,double map[maxn][maxn])//n为点的个数
{
    for (int k=1;k<=n;k++)//遍历中间节点
        for (int i=1;i<=n;i++)
            for (int j=1;j<=n;j++)
    if (map[i][k]+map[k][j]<map[i][j])
        map[i][j]=map[i][k]+map[k][j];
    return;
}

之后的map[i][j]就是i到j的最短路了

解释：当我中间节点遍历到第k个时，我已经求出了可以经过1到k-1这些点之后，从i到j的最短路；自己看代码体会一下这个过程