一、Floyd算法原理 Floyd算法是一个经典的动态规划算法，它又被称为插点法。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名。Floyd算法是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法,算法目标是寻找从点i到点j的最短路径。

从任意节点i到任意节点j的最短路径不外乎2种可能，1是直接从i到j，2是从i经过若干个节点k到j。所以，算法假设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的最短路径的距离。 二，时间复杂度为O(n^3)

三，Floyd算法理解

//&用来表示无穷

以Vi为源点，把Vi加到需要改的路径中间,若要把Vi加到其他路径的中间，则vi的那一行，那一列不变，以红色字体&为开头的那一列也不用变，剩下的地方对应着看，Vi那一行，那一列相加与原来的数进行比较，若比原来的数小，则替代原来的数，若比原来的数大，则空里不用改变。0的对角线也不需要改变。

以V1为源点

红色区域不需要改变，红色字体的&的一列也不需要改变，0对角线也不需要改变，剩下两个空需要改变，则看行列红色字体在空部分的交点，把他们相加与原来的数进行比较大小即可得出答案。V21+V13=2+3=59,不变。

以V3为源点

V13+V34=3+1=4