FLoyd算法（Floyd-Warshall algorithm）又称为弗洛伊德算法、差点法，是解决给定的加权图中顶点间的最短路径的一种算法，可以正确处理有向图或复权的最短路径问题，同时也被用于计算有向图的传递闭包。
    适用范围：无负权回路即可，边权可正可负，运行一次算法即可求得任意两点间最短路径。

    优缺点：
    Floyd算法适用于APSP(AllPairsShortestPaths)，是一种动态规划算法，稠密图效果最佳，边权可正可负。此算法简单有效，由于三重循环结构紧凑，对于稠密图，效率要高于执行|V|次Dijkstra算法。

    优点：容易理解，可以算出任意两个节点之间的最短路径，代码编写简单。
    缺点：时间复杂度高，不适合计算大量数据。
    时间复杂度：O(n^3)
    空间复杂度：O(n^2)

    算法解析：
    任意节点i到j的最短路径有两种可能：
    １、直接从ｉ到ｊ。
    ２、由ｉ经过若干个节点ｋ到ｊ。
    map(i, j)表示节点i到j最短路径的距离，对于每一个节点k，检查map(i, k) + map(k, j)小于map(i, j)，如果成立，map(i, j) = map(i, k) + map(k, j)。遍历每个k，每次更新的是除第k行和第k列的数。

    步骤：
    1、初始化map矩阵，矩阵中map[i][j]的距离为顶点i到顶点j的权值。如果i和j不相邻，则map[i][j] = +∞，如果i == j，则map[i][j] = 0.
    2、以顶点A（假设是第1个顶点）为中介点，若，a[i][j] > a[i][k] + a[k][j]，则设置a[i][j] = a[i][k] + a[k][j]。
    image.png
    无向图构建最短路径长度邻接矩阵：
    image.png
    image.png
    image.png
    image.png
    image.png
    image.png
    image.png
    image.png

    代码：

    1. for(int k = 1; k <= n; k++)
    2. {
    3.     for(int i = 1; i <= n; i++)
    4.     {
    5.         for(int j = 1; j <= n; j++)
    6.         {
    7.             if(dis[i][j] > dis[i][k] + dis[k][j])
    8.             {
    9.                 dis[i][j] = dis[i][k] + dis[k][j];
    10.                 //记录最短路径的数组
    11.                 path[i][j] = k;
    12.             }
    13.         }
    14.     }
    15. }