Floyd算法详解：求解所有点对最短路径

"弗洛伊德算法详解" 弗洛伊德算法，又称为弗洛伊德-沃什利算法，是一种用于求解图中所有点对之间最短路径的算法。该算法特别适用于处理带有负权边的图，尽管它的运行时间复杂度为O(n^3)，其中n是图中顶点的数量。与Dijkstra算法不同，Dijkstra算法只能解决单源最短路径问题，而弗洛伊德算法能够一次性解决所有点对间的最短路径问题。 Dijkstra算法在解决单源最短路径问题时，对于稀疏图（边的数量远小于顶点数量的平方）表现出较好的效率，因为其时间复杂度通常为O((E+V)logV)，其中E是边的数量。然而，当面对所有点对最短路径问题时，如果使用Dijkstra算法多次（n次，每顶点作为源点），总时间复杂度会变为O(n^2 * (E+V)logV)。这在大规模图中可能非常耗时。 相比之下，弗洛伊德算法通过迭代的方式逐步更新所有顶点之间的最短路径。算法的核心在于利用三层嵌套循环，分别遍历每一个中间节点k，从而检查是否存在通过k节点能使得两个顶点i和j之间的路径变得更短。具体步骤如下： 1. 初始化：设置一个n×n的矩阵dist，其中dist[i][j]表示顶点i到顶点j的初始距离。如果图中直接存在边(i, j)，则dist[i][j]为边的权重，否则为无穷大，表示没有直接连接的边。 2. 循环：对于每一个可能的中间节点k（从1到n），检查每一对顶点i和j（同样从1到n）： - 如果dist[i][k] + dist[k][j] < dist[i][j]，则更新dist[i][j] = dist[i][k] + dist[k][j]，这意味着找到了一条更短的路径通过节点k。 3. 结束：经过n次这样的迭代后，dist矩阵中的每个元素都将存储对应顶点对的最短路径。 弗洛伊德算法的优点在于它能够处理负权边，这是Dijkstra算法无法做到的。同时，对于稠密图（边的数量接近顶点数量的平方），由于其O(n^3)的时间复杂度，弗洛伊德算法通常比多次运行Dijkstra算法更快。然而，对于稀疏图，Dijkstra算法仍然是更好的选择。 理解弗洛伊德算法的关键在于掌握动态规划的思想，即通过不断迭代和更新，逐步找到全局最优解。在实际应用中，根据图的特性和需求，可以选择适合的最短路径算法。