除了Dijkstra算法和SPFA算法，另一种求最短路方法是Floyd算法。这个算法可以求出任意两点之间的最短路径长度，支持负边权，需要用邻接矩阵存图。
        算法缺点是耗时过大，时间复杂度O(n3)。
算法步骤:
        1 初始化dist数组，邻接节点dist值即为相邻边权值，否则为inf(无穷大)。
        2 枚举每一个节点，用这个节点作中介，更新所有节点对的最短路径值。
        最后dist即为最短路径数组，如果为inf则两点不连通。

        代码如下:

1
2
3
4
5
6
7
8
for (int k = 1; k <= n; k++) {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i != j && i != k && j != k)
		dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
        }
    }
}

算法正确性证明:
首先要清楚，最短路只有三种情况:
        1 两点直接相连且路径最短。
        2 两点经一个中介点路径最短。
        3 两点经多个中介点路径最短。
        情况1已经求出，且算法全程对这个值没有影响。情况2在枚举到中介点k时就已经求出了所有以k为单个中介的两点最短路。
        对于情况3，假设中介点为a1 < a2 < … < am。两点靠m个中介点获得最短路。令集合S={x，y，a1，a2…am}(x，y分别是源点和终点)。当k枚举到a1时，必然会更新这样一对属于情况2的节点对(ai，aj)，其中ai，aj∈S。这时可以看作是ai，aj直接相连而不经过a1，然后从S中清除a1，这样m个中介就减少至m-1个。后面的过程每次都使中介点减一，在枚举完成之前必可以将其转化为情况2并求出最短路径值。