最短路floyd算法

Floyd-Warshall算法是一种解决任意两点间最短路径的算法。它可以正确处理有向图或有向图中的负权（但不能存在负权回路）的最短路径问题。该算法的时间复杂度为O(N^3)，空间复杂度为O(N^2)。然而，Floyd-Warshall算法无法解决带有负权回路的图，因为这样的图没有最短路径。

在Floyd-Warshall算法中，我们通过不断更新图中所有顶点对之间的最短路径来找到最终的最短路径。该算法的核心思想是使用一个二维数组来保存每对顶点之间的最短路径长度，并通过遍历所有顶点来更新这个数组，直到获得最终结果。

下面是Floyd-Warshall算法的具体步骤：
1. 初始化一个二维数组dist，将其初始化为图中的边的权重，如果两个顶点之间没有边，则将其距离设置为无穷大。
2. 使用三层嵌套循环遍历所有顶点对(i, j)：
- 对于每个顶点对(i, j)，检查是否存在一个顶点k，使得从i到j经过k的路径更短。如果存在这样的顶点k，则更新dist[i][j]为dist[i][k] + dist[k][j]。
3. 最后，dist矩阵将包含每对顶点之间的最短路径长度。

请注意，Floyd-Warshall算法适用于有向图和无向图，且可以处理负权边（但不能有负权回路）。