Q2-1.Floyd算法求解各个顶点的最短距离

用Floyd算法求解下图各个顶点的最短距离。写出Floyd算法的伪代码和给出距离矩阵（顶点之间的最短距离矩阵）。

解析

Floyd算法是一个经典的动态规划算法，是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法。
通过一个图的权值矩阵求出它的每两点间的最短路径矩阵。
从任意节点i到任意节点j的最短路径，1是直接从i到j，2是从i经过若干个节点k到j。
从图的带权邻接矩阵开始，递归地进行n次更新，即由矩阵D(0)=A，按一个公式，构造出矩阵D(1)；又用同样地公式由D(1)构造出D(2)；……；最后又用同样的公式由D(n-1)构造出矩阵D(n)。
算法假设Dis(i,j)为节点u到节点v的最短路径的距离，对于每一个节点k，算法检查Dis(i,k) +Dis(k,j) < Dis(i,j)是否成立，如果成立，证明从i到k再到j的路径比i直接到j的路径短，便设置Dis(i,j) = Dis(i,k) + Dis(k,j)，这样一来，当遍历完所有节点k，Dis(i,j)中记录的便是i到j的最短路径的距离。

设计

for(u = 0; u < G.vexnum; ++ u)
    for(v = 0; v < G.vexnum; ++ v)
        for(w = 0; w < G.vexnum; ++ w)
            if(D[v][u] + D[u][w] < D[v][w])// 从v经u到w的一条路径更短
                D[v][w] = D[v][u] + D[u][w]; 

分析

该代码的空间复杂度为O(n^2)，
时间复杂度为O(n^3)

源码

https://github.com/pt0918/-/blob/master/Floyd.cpp