OI-Knowledge：最短路——Floyd算法

在图论中，寻找所有顶点对之间的最短路径是一个常见问题。Floyd-Warshall 算法是一种解决这个问题的有效方法。本文将介绍 Floyd-Warshall 算法的基本概念、工作原理，并提供相应的 C++ 实现代码。

什么是 Floyd-Warshall 算法？

Floyd-Warshall 算法是一种用于寻找加权图中所有顶点对之间最短路径的动态规划算法。该算法的主要思想是通过中间顶点迭代更新最短路径长度，从而逐步优化路径。

算法步骤

初始化：创建一个距离矩阵 dist，其中 dist[i][j] 表示顶点 i 到顶点 j 的初始距离。如果两顶点之间没有边，则距离设为无穷大（通常用一个大数表示）。
迭代更新：对于每个中间顶点 k，更新所有顶点对 (i, j) 的距离。如果通过顶点 k 的路径比当前已知路径更短，则更新 dist[i][j] 的值。
结果输出：最终的距离矩阵 dist 即为所有顶点对之间的最短路径长度。

算法复杂度

Floyd-Warshall 算法的时间复杂度为 O(V^3)，其中 V 是图中的顶点数。尽管时间复杂度较高，但该算法在稠密图（边数接近于顶点数平方）中表现良好。

代码实现

以下是 Floyd-Warshall 算法的 C++ 实现代码：

#include <iostream>
#include <vector>
#include <limits>

const int INF = std::numeric_limits<int>::max();

// Floyd-Warshall算法实现
void floydWarshall(std::vector<std::vector<int>>& graph) {
    int V = graph.size();
    std::vector<std::vector<int>> dist = graph;

    // 三重循环，更新距离矩阵
    for (int k = 0; k < V; ++k) {
        for (int i = 0; i < V; ++i) {
            for (int j = 0; j < V; ++j) {
                if (dist[i][k] != INF && dist[k][j] != INF && dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }

    // 输出最终的距离矩阵
    for (int i = 0; i < V; ++i) {
        for (int j = 0; j < V; ++j) {
            if (dist[i][j] == INF) {
                std::cout << "INF ";
            } else {
                std::cout << dist[i][j] << " ";
            }
        }
        std::cout << std::endl;
    }
}

int main() {
    std::vector<std::vector<int>> graph = {
        {0, 3, INF, 7},
        {8, 0, 2, INF},
        {5, INF, 0, 1},
        {2, INF, INF, 0}
    };

    floydWarshall(graph);
    return 0;
}

代码解析

定义常量 INF：用于表示无穷大。
初始化图的邻接矩阵 graph：每个元素表示顶点之间的距离。如果没有直接边，则距离为 INF。
调用 floydWarshall 函数：传入图的邻接矩阵进行处理。
更新距离矩阵：通过三重循环迭代更新距离矩阵中的值。
输出结果：打印最终的最短路径矩阵。

总结

Floyd-Warshall 算法是一种简单但功能强大的算法，可以有效地解决所有顶点对之间的最短路径问题。通过本文的介绍和代码示例，希望读者能够更好地理解并应用这一算法。