743. 网络延迟时间

Medium

题目描述

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

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

示例 1：

输入：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) 对都互不相同（即，不含重复边）

解题思路

这是一个典型的单源最短路径问题，需要找到从起始节点 k 到所有其他节点的最短路径，然后返回最长的那条路径时间。

核心思路：

构建邻接表表示图的结构
使用 Dijkstra 算法计算从节点 k 到所有节点的最短距离
检查是否所有节点都可达，如果是则返回最大距离，否则返回 -1

算法步骤：

将 times 转换为邻接表，方便查找每个节点的邻居
初始化距离数组，起始节点距离为 0，其他节点距离为无穷大
使用优先队列（最小堆）进行 Dijkstra 算法：
- 每次取出当前距离最小的未访问节点
- 更新其所有邻居的最短距离
- 将更新后的邻居加入优先队列
遍历完成后，检查距离数组：
- 如果存在无穷大的距离，说明有节点不可达，返回 -1
- 否则返回距离数组中的最大值

时间复杂度分析： Dijkstra 算法的时间复杂度为 O((V+E)logV)，其中 V 是节点数，E 是边数。

代码实现

class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        // 构建邻接表
        vector<vector<pair<int, int>>> graph(n + 1);
        for (auto& time : times) {
            graph[time[0]].push_back({time[1], time[2]});
        }
        
        // 距离数组，初始化为无穷大
        vector<int> dist(n + 1, INT_MAX);
        dist[k] = 0;
        
        // 优先队列：{距离, 节点}
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        pq.push({0, k});
        
        while (!pq.empty()) {
            auto [d, u] = pq.top();
            pq.pop();
            
            // 如果当前距离大于已知最短距离，跳过
            if (d > dist[u]) continue;
            
            // 更新邻居节点
            for (auto& [v, w] : graph[u]) {
                if (dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    pq.push({dist[v], v});
                }
            }
        }
        
        // 找到最大距离
        int maxDist = 0;
        for (int i = 1; i <= n; i++) {
            if (dist[i] == INT_MAX) return -1;
            maxDist = max(maxDist, dist[i]);
        }
        
        return maxDist;
    }
};

class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        import heapq
        
        # 构建邻接表
        graph = defaultdict(list)
        for u, v, w in times:
            graph[u].append((v, w))
        
        # 距离数组
        dist = [float('inf')] * (n + 1)
        dist[k] = 0
        
        # 优先队列：(距离, 节点)
        pq = [(0, k)]
        
        while pq:
            d, u = heapq.heappop(pq)
            
            # 如果当前距离大于已知最短距离，跳过
            if d > dist[u]:
                continue
            
            # 更新邻居节点
            for v, w in graph[u]:
                if dist[u] + w < dist[v]:
                    dist[v] = dist[u] + w
                    heapq.heappush(pq, (dist[v], v))
        
        # 检查是否所有节点都可达
        max_dist = max(dist[1:])
        return max_dist if max_dist != float('inf') else -1

public class Solution {
    public int NetworkDelayTime(int[][] times, int n, int k) {
        // 构建邻接表
        var graph = new Dictionary<int, List<(int, int)>>();
        for (int i = 1; i <= n; i++) {
            graph[i] = new List<(int, int)>();
        }
        
        foreach (var time in times) {
            graph[time[0]].Add((time[1], time[2]));
        }
        
        // 距离数组
        var dist = new int[n + 1];
        Array.Fill(dist, int.MaxValue);
        dist[k] = 0;
        
        // 优先队列：(距离, 节点)
        var pq = new PriorityQueue<(int dist, int node), int>();
        pq.Enqueue((0, k), 0);
        
        while (pq.Count > 0) {
            var (d, u) = pq.Dequeue();
            
            // 如果当前距离大于已知最短距离，跳过
            if (d > dist[u]) continue;
            
            // 更新邻居节点
            foreach (var (v, w) in graph[u]) {
                if (dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    pq.Enqueue((dist[v], v), dist[v]);
                }
            }
        }
        
        // 找到最大距离
        int maxDist = 0;
        for (int i = 1; i <= n; i++) {
            if (dist[i] == int.MaxValue) return -1;
            maxDist = Math.Max(maxDist, dist[i]);
        }
        
        return maxDist;
    }
}

var networkDelayTime = function(times, n, k) {
    // 构建邻接表
    const graph = new Map();
    for (let i = 1; i <= n; i++) {
        graph.set(i, []);
    }

    for (const [u, v, w] of times) {
        graph.get(u).push([v, w]);
    }

    // 距离数组
    const dist = new Array(n + 1).fill(Infinity);
    dist[k] = 0;

    // 优先队列：[距离, 节点]
    const heap = [[0, k]];

    const push = (item) => {
        heap.push(item);
        let index = heap.length - 1;
        while (index > 0) {
            const parent = Math.floor((index - 1) / 2);
            if (heap[parent][0] <= heap[index][0]) break;
            [heap[parent], heap[index]] = [heap[index], heap[parent]];
            index = parent;
        }
    };

    const pop = () => {
        const result = heap[0];
        const last = heap.pop();
        if (heap.length > 0) {
            heap[0] = last;
            let index = 0;
            while (true) {
                let smallest = index;
                const left = index * 2 + 1;
                const right = left + 1;
                if (left < heap.length && heap[left][0] < heap[smallest][0]) {
                    smallest = left;
                }
                if (right < heap.length && heap[right][0] < heap[smallest][0]) {
                    smallest = right;
                }
                if (smallest === index) break;
                [heap[smallest], heap[index]] = [heap[index], heap[smallest]];
                index = smallest;
            }
        }
        return result;
    };

    while (heap.length > 0) {
        const [d, u] = pop();

        // 如果当前距离大于已知最短距离，跳过
        if (d > dist[u]) continue;

        // 更新邻居节点
        for (const [v, w] of graph.get(u)) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                push([dist[v], v]);
            }
        }
    }

    // 找到最大距离
    let maxDist = 0;
    for (let i = 1; i <= n; i++) {
        if (dist[i] === Infinity) return -1;
        maxDist = Math.max(maxDist, dist[i]);
    }

    return maxDist;
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

解法	时间复杂度	空间复杂度
Dijkstra算法	O((V+E)logV)	O(V+E)

其中 V 是节点数量 n，E 是边数量 times.length。时间复杂度主要来自优先队列的操作，空间复杂度主要用于存储邻接表和距离数组。

题目描述#

解题思路#

代码实现#

复杂度分析#

相关题目#

题目描述

解题思路

代码实现

复杂度分析

相关题目