面试题：C++ 基于 Floyd 算法的动态图最短路径更新

Question

假设在一个动态图中，图的边权会动态变化。请基于 C++ 的 Floyd 算法设计一种机制，当图中的某条边权发生变化时，能够高效地更新任意两点之间的最短路径。描述整体设计思路，包括数据结构的选择和更新算法的实现步骤，并给出关键部分的 C++ 代码。

Answer 1

设计思路

1. 数据结构选择：
   • 使用二维数组 dist 来存储任意两点之间的最短距离，初始时 dist[i][j] 表示从顶点 i 到顶点 j 的最短路径长度。如果 i 和 j 之间没有直接边相连，则 dist[i][j] 设为一个较大的值（例如 INT_MAX）。
   • 使用二维数组 path 来记录最短路径上的前驱节点，用于在需要时还原最短路径。
2. 更新算法实现步骤：
   • 当某条边 (u, v) 的权值发生变化时，首先更新 dist[u][v] 和 dist[v][u]（如果图是无向图）。
   • 然后对所有顶点 k，检查是否可以通过更新后的边 (u, v) 来更新 dist[i][j]，即检查 dist[i][u] + dist[u][v] + dist[v][j] < dist[i][j] 是否成立，如果成立，则更新 dist[i][j] 和 path[i][j]。

关键部分 C++ 代码

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

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

// 初始化Floyd算法的数据结构
void initFloyd(std::vector<std::vector<int>>& dist, std::vector<std::vector<int>>& path, int n) {
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (i == j) {
                dist[i][j] = 0;
            } else {
                dist[i][j] = INF;
            }
            path[i][j] = -1;
        }
    }
}

// 基于Floyd算法的边权更新函数
void updateFloyd(std::vector<std::vector<int>>& dist, std::vector<std::vector<int>>& path, int u, int v, int newWeight) {
    // 更新边权
    dist[u][v] = newWeight;
    dist[v][u] = newWeight;

    // 更新最短路径
    int n = dist.size();
    for (int k = 0; k < n; ++k) {
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (dist[i][u] != INF && dist[u][v] != INF && dist[v][j] != INF &&
                    dist[i][u] + dist[u][v] + dist[v][j] < dist[i][j]) {
                    dist[i][j] = dist[i][u] + dist[u][v] + dist[v][j];
                    path[i][j] = path[u][j];
                }
            }
        }
    }
}