面试题：C++ 优化 Floyd 算法空间复杂度

Question

在 C++ 中，Floyd 算法通常使用三维数组来记录中间节点的信息以计算最短路径，空间复杂度为 O(n^3)。请你优化该算法，使其空间复杂度降为 O(n^2)，同时保持时间复杂度 O(n^3) 不变。说明优化思路并给出优化后的 C++ 代码。

Answer 1

优化思路

Floyd算法中，使用三维数组记录中间节点信息导致空间复杂度为O(n^3)。实际上，在更新最短路径时，每次只需要当前轮次之前的信息，因此可以将三维数组优化为二维数组。在更新路径时，直接在原二维距离矩阵上进行操作，每次更新时利用当前中间节点来尝试更新任意两点之间的距离。

优化后的C++代码

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

void floydWarshall(std::vector<std::vector<int>>& graph) {
    int n = graph.size();
    // 初始化距离矩阵，这里graph同时作为距离矩阵
    std::vector<std::vector<int>> dist = graph;

    for (int k = 0; k < n; ++k) {
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (dist[i][k] != std::numeric_limits<int>::max() && dist[k][j] != std::numeric_limits<int>::max()) {
                    dist[i][j] = std::min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
    }

    // 输出最短路径矩阵
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (dist[i][j] == std::numeric_limits<int>::max()) {
                std::cout << "INF ";
            } else {
                std::cout << dist[i][j] << " ";
            }
        }
        std::cout << std::endl;
    }
}

int main() {
    // 示例图的邻接矩阵，INF表示无穷大
    std::vector<std::vector<int>> graph = {
        {0, 5, std::numeric_limits<int>::max(), 10},
        {std::numeric_limits<int>::max(), 0, 3, std::numeric_limits<int>::max()},
        {std::numeric_limits<int>::max(), std::numeric_limits<int>::max(), 0, 1},
        {std::numeric_limits<int>::max(), std::numeric_limits<int>::max(), std::numeric_limits<int>::max(), 0}
    };

    floydWarshall(graph);
    return 0;
}