Floyd算法又称为插点法，是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法，与Dijkstra算法类似。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名。 Floyd算法用于多源最短路径的求解，算出来的是所有的节点到其余各节点之间的最短距离。

与迪杰斯特拉算法区别：迪杰斯特拉算法通过选定的被访问顶点，求出从出发访问顶点到其他顶点的最短路径； 弗洛伊德算法中每一个顶点都是出发访问点，所以需要将每一个顶点看做被访问顶点，求出从每一个顶点到其他顶点的最短路径。

Floyd算法，则修正了dijkstra算法对于边权为负问题的不足，引入了一个外循环，来遍历每个点，从而查询该点是不是在i和j之间，这样的话，无论边权为负值还是正值，都会被考虑进去。对于邻接矩阵A来说，在 k − 1 k-1 k−1次迭代后， A k − 1 [ i ] [ j ] A_{k-1}[i][j] Ak−1​[i][j]为所有从顶点 i i i到 j j j且不经过 k k k之后的顶点的最小长度，有可能经过 k k k之前的点。所以在遍历过程中需要比较 A [ i ] [ j ] A[i][j] A[i][j]与 A [ i ] [ k ] + A [ k ] [ j ] A[i][k]+A[k][j] A[i][k]+A[k][j]的大小，取小值，表示比较经过 k k k点与不经过 k k k点的路径长度大小。

基本思想：

设置顶点 v i v_i vi​到顶点 v k v_k vk​的最短路径已知为 L i k L_{ik} Lik​，顶点 v k v_k vk​到 v j v_j vj​的最短路径已知为 L k j L_{kj} Lkj​，顶点 v i v_i vi​到 v j v_j vj​的路径为 L i j L_{ij} Lij​ 则 v i v_i vi​到 v j v_j vj​的最短路径为： m i n ( ( L i k + L k j ) min((L_{ik}+L_{kj}) min((Lik​+Lkj​), L i j L_{ij} Lij​(直连))， v k v_k vk​的取值为图中所有顶点，则可获得 v i v_i vi​到 v j v_j vj​的最短路径。至于 v i v_i vi​到 v k v_k vk​的最短路径 L i k L_{ik} Lik​或者 v k v_k vk​到 v j v_j vj​的最短路径 L k j L_{kj} Lkj​，是以同样的方式获得

转移方程：

其中dis[i][j]：为 i i i到 j j j的最短路径。 dis[i][k] 为 i i i到 k k k的最短路径 dis[k][j] 为 k k k到 j j j的最短路径.

重复上述直到最后插点试探完成。最终dis数组中存放的就是任意两个结点之间的最短距离

D(0)表示不包含中间节点，即给定图的原始权重矩阵； D(1)表示加入一个中间节点a； D(2)表示在D(1)的基础上再加入一个中间节点b； D(3)表示在D(2)的基础上再加入一个中间节点c； D(4)表示在D(3)的基础上再加入一个中间节点d，这时就可得到最终结果。 每次加入新结点都要更新所有顶点之间的最短距离，直到所有顶点均可以作为中间顶点之后，才算更新完毕，即可得到最终结果。