floyd算法

Floyd算法，也叫插点法，是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法，与Dijkstra算法类似。

Floyd算法的基本思想是：对于给定的加权图，初始化时，每个顶点之间都有一条直接的边或者没有边，然后逐渐通过中间节点来更新每个顶点之间的路径长度，直到所有顶点之间的最短路径都被找出。

具体实现过程中，Floyd算法使用一个二维数组D[][]来记录任意两个顶点之间的最短路径长度，同时使用另一个二维数组path[][]来记录任意两个顶点之间的最短路径上的前驱节点，从而可以方便地还原最短路径。

Floyd算法的时间复杂度为O(N^3)，其中N为图中顶点的个数。它适用于求解任意两点之间的最短路径，但是对于边权为负值的图，则无法使用Floyd算法。

以下是Floyd算法的伪代码实现：

procedure FloydWarshall (graph[][], dist[][], path[][])
   for i from 1 to n
      for j from 1 to n
         dist[i][j] ← graph[i][j]
         if i = j or graph[i][j] = ∞
            path[i][j] ← 0
         else
            path[i][j] ← i
   for k from 1 to n
      for i from 1 to n
         for j from 1 to n
            if dist[i][j] > dist[i][k] + dist[k][j]
               dist[i][j] ← dist[i][k] + dist[k][j]
               path[i][j] ← path[k][j]