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 到所有其他节点的最短路径，然后返回最长的那条路径时间。

核心思路：

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

算法步骤：

  1. 将 times 转换为邻接表，方便查找每个节点的邻居
  2. 初始化距离数组，起始节点距离为 0，其他节点距离为无穷大
  3. 使用优先队列（最小堆）进行 Dijkstra 算法：
    • 每次取出当前距离最小的未访问节点
    • 更新其所有邻居的最短距离
    • 将更新后的邻居加入优先队列
  4. 遍历完成后，检查距离数组：
    • 如果存在无穷大的距离，说明有节点不可达，返回 -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 pq = [[0, k]]; // [距离, 节点]
    
    while (pq.length > 0) {
        // 手动找到最小距离的节点
        let minIdx = 0;
        for (let i = 1; i < pq.length; i++) {
            if (pq[i][0] < pq[minIdx][0]) {
                minIdx = i;
            }
        }
        
        const [d, u] = pq.splice(minIdx, 1)[0];
        
        // 如果当前距离大于已知最短距离，跳过
        if (d > dist[u]) continue;
        
        // 更新邻居节点
        for (const [v, w] of graph.get(u)) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push([dist[v], v]);
            }
        }
    }
    
    // 找到最大距离
    let maxDist = 0;
    for (let i = 1; i <= n; i++) {
        if (dist[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

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

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

相关题目