跳到主要内容

LeetCode 743. 网络延迟时间

本节目标

用邻接表和最小堆 Dijkstra 计算信号到达所有节点的最短延迟。

这是最短路的稀疏图 Dijkstra 母题：从 k 发出的信号到达所有节点所需的最长最短路，就是答案。

查看 LeetCode 原题

题意与约束​

每条 times[i] = [u, v, w] 是正权有向边。若任一节点从 k 不可达，返回 -1；否则返回所有 dist 的最大值。

直接思路与瓶颈​

沿用矩阵版 Dijkstra 也能得到正确答案，但每一轮都扫描全部 n 个点找最小候选；本题输入只列出真实边，稀疏图中大量矩阵位置根本不存在，O(n²) 选点会浪费工作。枚举信号路径则同样会遇到路径数膨胀。应只从真实出边扩展候选，并快速取出当前最短候选。

图模型与算法推导​

把 times 建为有向邻接表，只保存真实存在的边。最小堆存储 (候选距离, 顶点)；每次改善 dist[v] 就把新候选入堆。同一顶点可能留下旧候选，弹出时若堆中距离不等于当前 dist[v]，它已经被更短路径取代，必须跳过。其余弹出项正是当前最短候选，可以松弛该点的出边。结束后取所有最终距离的最大值，表示最后一个收到信号的节点。

正确性依据​

堆中每个未过期条目都是某条从 k 出发路径的长度，因此 dist 始终是已知路径给出的上界。弹出未过期的最小条目 (d,u) 时，若存在一条更短的到 u 的路径，它首次穿出已经按不增距离处理完的顶点集合时，会产生一个小于 d 的候选并已入堆，矛盾；故 d=dist[u] 已正确。对 u 的每条出边松弛会加入所有以 u 为最后一段的更优路径。过期条目只对应已经被更小上界替代的旧路径，跳过不影响任何最优路径。于是所有可达点距离正确；若仍有无穷大距离，就确有节点收不到信号。

样例执行过程​

输入 times=[[1,2,10],[1,2,3],[1,3,8],[2,3,2],[3,4,1]]，n=4，k=1。其中 1→2 有权重 10 和 3 两条并行边，邻接表还包含 1→3=8、2→3=2、3→4=1。以下堆状态按距离从小到大列出所有待处理项。

  1. 初始 dist=[0,∞,∞,∞]（依次对应节点 1 至 4），堆为 [(0,1)]。
  2. 弹出 (0,1)。依次扫描三条出边：先由 1→2=10 得到 dist[2]=10 并压入 (10,2)；再由更轻的并行边改为 dist[2]=3 并压入 (3,2)；最后令 dist[3]=8 并压入 (8,3)。此时 dist=[0,3,8,∞]，堆为 [(3,2),(8,3),(10,2)]。
  3. 弹出 (3,2)，经 2→3=2 得到候选 5，把 dist[3] 从 8 改为 5，并压入 (5,3)。此时 dist=[0,3,5,∞]，堆为 [(5,3),(8,3),(10,2)]。
  4. 弹出 (5,3)，经 3→4=1 得到 dist[4]=6，压入 (6,4)。此时 dist=[0,3,5,6]，堆为 [(6,4),(8,3),(10,2)]。
  5. 弹出 (6,4)，节点 4 没有出边。随后弹出 (8,3)，因为 8 != dist[3]，它是旧路径留下的过期项，直接跳过；再弹出 (10,2)，因为 10 != dist[2]，同样直接跳过。
  6. 堆为空，四个节点最短距离的最大值是 6，最终答案为 6。

代码实现​

C++17
#include <algorithm>
#include <functional>
#include <queue>
#include <utility>
#include <vector>
using namespace std;

class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        vector<vector<pair<int, long long>>> graph(n + 1);
        for (const auto& edge : times) {
            graph[edge[0]].push_back({edge[1], static_cast<long long>(edge[2])});
        }

        const long long INF = 1LL << 60;
        vector<long long> dist(n + 1, INF);
        priority_queue<pair<long long, int>, vector<pair<long long, int>>,
                       greater<pair<long long, int>>> heap;
        dist[k] = 0;
        heap.push({0, k});

        while (!heap.empty()) {
            auto [distance, vertex] = heap.top();
            heap.pop();
            if (distance != dist[vertex]) continue;

            for (const auto& [nxt, weight] : graph[vertex]) {
                const long long candidate = distance + weight;
                if (candidate < dist[nxt]) {
                    dist[nxt] = candidate;
                    heap.push({candidate, nxt});
                }
            }
        }

        long long answer = 0;
        for (int vertex = 1; vertex <= n; vertex++) {
            if (dist[vertex] == INF) return -1;
            answer = max(answer, dist[vertex]);
        }
        return static_cast<int>(answer);
    }
};

复杂度分析​

建图 O(m)；每次成功松弛会入堆，时间为 O((n + m) log n)，邻接表、距离和堆使用 O(n + m) 空间。

边界与易错点​

  • 图是有向的，不能补反向边。
  • 不能只在首次出堆后假定没有旧记录；用距离比较跳过过期项。
  • 答案是全部节点最短距离的最大值，不是某一条路径的最大边权。
  • 存在无穷大距离时必须返回 -1。

模式迁移​

凡是“非负权、单源、稀疏图”的题，都可复用这套邻接表、堆与过期项检查；仅改变起点、终点或最终聚合方式。