跳转至

网络延迟时间

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

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

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

题解

这是经典的最短路问题。

我们只需要考虑从某个节点 K 发出一个信号，到其他所有节点的最短路path_i，然后再取最大值即可：

res = max(path_i for i in 1:n)

Dijsktra

Dijsktra算法是图论中经典的最短路算法，可以计算从单个节点出发到其他所有节点的最短路。

注：Dijsktra 不能解决边权有负值的情况

基本思想：

  • 设一个集合S，表示已经找到最短路的节点【初始化仅有源点】
  • 从V-S集合（未确定最短路的节点）中找到距离最小的节点u
  • 把u加入集合S
  • 遍历V-S集合，更新距离：dist[v] = min(dist[v], dist[u] + G[u][v])
    • 注：距离初始化为每个节点到源点到距离（如果没有边就初始化为无穷大）

显然，算法复杂度为O(N^2)

在本题的代码如下：

class Solution:
    def networkDelayTime(self, times, n: int, k: int) -> int:
        # 所有的节点
        unvisited = set(range(1, n + 1))
        # 记录所有的边
        paths = {}
        for s, t, value in times:
            paths[s] = {**paths.get(s, {}), t: value}
        # d字典记录从k到每个阶段的最短路
        inf = float("inf")
        d = {node: inf for node in unvisited}
        # 把k节点标记为访问过
        visited = {k}
        d[k] = 0
        unvisited.remove(k)
        # Dijsktra算法
        while unvisited:
            # update distance
            for s in visited:
                # 如果有边可以尝试
                if s not in paths:
                    continue
                # 就试着走一下
                for t in paths[s]:
                    d[t] = min(d[t], d[s] + paths[s][t])
            # 选取一个最优节点加入
            best_next = min({x: d[x] for x in unvisited}, key=lambda x: d[x])
            visited.add(best_next)
            unvisited.remove(best_next)
        # 整个网络的最小广播时间是所有最短路的最大值
        res = max(d.values())
        return res if res != inf else -1

Leetcode的题解还给出了使用堆优化的版本：

class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        g = [[] for _ in range(n)]
        for x, y, time in times:
            g[x - 1].append((y - 1, time))

        dist = [float('inf')] * n
        dist[k - 1] = 0
        q = [(0, k - 1)]
        while q:
            time, x = heapq.heappop(q)
            if dist[x] < time:
                continue
            for y, time in g[x]:
                if (d := dist[x] + time) < dist[y]:
                    dist[y] = d
                    heapq.heappush(q, (d, y))

        ans = max(dist)
        return ans if ans < float('inf') else -1

# 作者：力扣官方题解
# 链接：https://leetcode.cn/problems/network-delay-time/solutions/909575/wang-luo-yan-chi-shi-jian-by-leetcode-so-6phc/
# 来源：力扣（LeetCode）
# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
最后更新: 2025-08-03 03:17:56
创建日期: 2025-08-03 03:17:56

广告

人要恰饭的嘛🤑🤑

评论