floyd算法求最短路径

Floyd算法是一种经典的动态规划算法，用于解决有向图或者有权图中多源点的最短路径问题。它的时间复杂度为O(n^3)，其中n是图中节点的个数。

Floyd算法的基本思想是：对于图中的任意两个节点，如果它们之间存在一条边，则它们之间的最短路径就是这条边的权重。否则，它们之间的最短路径就是通过中间节点的最短路径。因此，我们可以使用动态规划的思想来求解任意两个节点之间的最短路径。

具体来说，我们可以定义一个二维数组dist，其中dist[i][j]表示节点i到节点j的最短路径。然后，我们可以使用三重循环来更新数组dist。每次循环中，我们枚举中间节点k，如果从节点i到节点j经过中间节点k的路径比当前的最短路径更短，则更新dist[i][j]的值。

下面是Floyd算法的伪代码：

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]

其中，dist[i][j]表示节点i到节点j的最短路径。在每一次循环中，我们枚举中间节点k，如果从节点i到节点j经过中间节点k的路径比当前的最短路径更短，则更新dist[i][j]的值。最终，dist数组中存储的就是任意两个节点之间的最短路径。

需要注意的是，Floyd算法只适用于稠密图，即边的数量相对于节点数目比较大的图。对于稀疏图，我们通常使用Dijkstra算法或者Bellman-Ford算法来求解最短路径问题。