网络延迟时间

2024-11-25

题目：

有 n 个网络节点，标记为 1 到 n。

给你一个列表 times，表示信号经过 有向 边的传递时间。 times[i] = (ui, vi, wi)，其中 ui 是源节点，vi 是目标节点， wi 是一个信号从源节点传递到目标节点的时间。

现在，从某个节点 K 发出一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回 -1 。

示例 1：

img

输入：times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
输出：2

示例 2：

输入：times = [[1,2,1]], n = 2, k = 1
输出：1

示例 3：

输入：times = [[1,2,1]], n = 2, k = 2
输出：-1

提示：

  • 1 <= k <= n <= 100
  • 1 <= times.length <= 6000
  • times[i].length == 3
  • 1 <= ui, vi <= n
  • ui != vi
  • 0 <= wi <= 100
  • 所有 (ui, vi) 对都 互不相同（即，不含重复边）

思路：

定义 g[i][j] 表示节点 i 到节点 j 这条边的边权。如果没有 i 到 j 的边，则 g[i][j]=∞。

定义 dis[i] 表示起点 k 到节点 i 的最短路长度，一开始 dis[k]=0，其余 dis[i]=∞ 表示尚未计算出。

我们的目标是计算出最终的 dis 数组。
	首先更新起点 k 到其邻居 y 的最短路，即更新 dis[y] 为 g[k][y]。
	然后取除了起点 k 以外的 dis[i] 的最小值，假设最小值对应的节点是 3。此时可以断言：dis[3] 已经是 k 到 3 的最短路长度，不可能有其它 k 到 3 的路径更短！反证法：假设存在更短的路径，那我们一定会从 k 出发经过一个点 u，它的 dis[u] 比 dis[3] 还要小，然后再经过一些边到达 3，得到更小的 dis[3]。但 dis[3] 已经是最小的了，并且图中没有负数边权，所以 u 是不存在的，矛盾。故原命题成立，此时我们得到了 dis[3] 的最终值。
	用节点 3 到其邻居 y 的边权 g[3][y] 更新 dis[y]：如果 dis[3]+g[3][y]<dis[y]，那么更新 dis[y] 为 dis[3]+g[3][y]，否则不更新。
	然后取除了节点 k,3 以外的 dis[i] 的最小值，重复上述过程。
	由数学归纳法可知，这一做法可以得到每个点的最短路。当所有点的最短路都已确定时，算法结束。

写法一：朴素 Dijkstra（适用于稠密图）

代码：

对于本题，在计算最短路时，如果发现当前找到的最小最短路等于 ∞，说明有节点无法到达，可以提前结束算法，返回 −1。

如果所有节点都可以到达，返回 max(dis)。

代码实现时，节点编号改成从 0 开始。

class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        vector<vector<int>> g(n, vector<int>(n, INT_MAX / 2)); // 邻接矩阵
        for (auto& t : times) {
            g[t[0] - 1][t[1] - 1] = t[2];
        }

        vector<int> dis(n, INT_MAX / 2), done(n);
        dis[k - 1] = 0;
        while (true) {
            int x = -1;
            for (int i = 0; i < n; i++) {
                if (!done[i] && (x < 0 || dis[i] < dis[x])) {
                    x = i;
                }
            }
            if (x < 0) {
                return ranges::max(dis);
            }
            if (dis[x] == INT_MAX / 2) { // 有节点无法到达
                return -1;
            }
            done[x] = true; // 最短路长度已确定（无法变得更小）
            for (int y = 0; y < n; y++) {
                // 更新 x 的邻居的最短路
                dis[y] = min(dis[y], dis[x] + g[x][y]);
            }
        }
    }
};

写法二：堆优化 Dijkstra（适用于稀疏图）

寻找最小值的过程可以用一个最小堆来快速完成：
	一开始把 (dis[k],k) 二元组入堆。
	当节点 x 首次出堆时，dis[x] 就是写法一中寻找的最小最短路。
	更新 dis[y] 时，把 (dis[y],y) 二元组入堆。

注意，如果一个节点 x 在出堆前，其最短路长度 dis[x] 被多次更新，那么堆中会有多个重复的 x，并且包含 x 的二元组中的 dis[x] 是互不相同的（因为我们只在找到更小的最短路时才会把二元组入堆）。

所以写法一中的 done 数组可以省去，取而代之的是用出堆的最短路值（记作 dx）与当前的 dis[x] 比较，如果 dx>dis[x] 说明 x 之前出堆过，我们已经更新了 x 的邻居的最短路，所以这次就不用更新了，继续外层循环。

答疑
问：为什么代码要判断 dx > dis[x]？

答：对于同一个 x，例如先入堆一个比较大的 dis[x]=10，后面又把 dis[x] 更新成 5，之后这个 5 会先出堆，然后再把 10 出堆。10 出堆时候是没有必要去更新周围邻居的最短路的，因为 5 出堆之后，就已经把邻居的最短路更新过了，用 10 是无法把邻居的最短路变得更短的，所以直接 continue。

代码：

class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        vector<vector<pair<int, int>>> g(n); // 邻接表
        for (auto& t : times) {
            g[t[0] - 1].emplace_back(t[1] - 1, t[2]);
        }

        vector<int> dis(n, INT_MAX);
        dis[k - 1] = 0;
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
        pq.emplace(0, k - 1);
        while (!pq.empty()) {
            auto [dx, x] = pq.top();
            pq.pop();
            if (dx > dis[x]) { // x 之前出堆过
                continue;
            }
            for (auto &[y, d] : g[x]) {
                int new_dis = dx + d;
                if (new_dis < dis[y]) {
                    dis[y] = new_dis; // 更新 x 的邻居的最短路
                    pq.emplace(new_dis, y);
                }
            }
        }
        int mx = ranges::max(dis);
        return mx < INT_MAX ? mx : -1;
    }
};