Network Delay Time
一个网络有 n 个节点，编号从 1 到 n。链接 times[i] = [u, v, w] 会将信号从节点 u 传到节点 v，耗时 w 个单位时间，且只能沿这个方向传输。
一个信号在时间 0 时从节点 k 出发，并沿着所有能到达的链接传播。返回最后一个节点接收到信号的时间；如果有节点始终收不到信号，则返回 -1。
函数
- timesinteger-2d-array
- 有向边，每条表示为 [u, v, w]
- ninteger
- 节点数
- kinteger
- 发送信号的节点
- 返回值integer
- 最后一个节点收到信号的时间，或者 -1
约束条件
2 ≤ n ≤ 30001 ≤ times.length ≤ 4000times[i].length = 31 ≤ u, v ≤ n并且u ≠ v0 ≤ w ≤ 100- 没有两条链接同时共享相同的
u和v。 1 ≤ k ≤ n
示例
- 输入
- times = [[1, 2, 4], [1, 3, 1], [3, 2, 2], [2, 4, 1]]n = 4k = 1
- 输出
- 4
- 解释
- 直接链接在时间 4 时到达节点 2，但经过节点 3 的路径会在 1 + 2 = 3 时到达。节点 4 最后收到信号，时间为 3 + 1 = 4。
- 输入
- times = [[1, 2, 3], [3, 1, 2]]n = 3k = 1
- 输出
- -1
- 解释
- 节点 2 在时间 3 收到信号，但与节点 3 相连的唯一链路是从 3 到 1。节点 3 始终收不到信号，所以答案是 -1。
- 输入
- times = [[2, 1, 5], [2, 3, 0], [3, 1, 2]]n = 3k = 2
- 输出
- 2
- 解释
- 到节点 3 的链路耗时为 0，因此节点 3 在时间 0 收到信号。然后节点 1 在 0 + 2 = 2 时收到信号，比它的直连链路耗时 5 更早。
进阶
假设信号在经过 m 条链路后会消失。如何在这个限制下，找出最后一个节点收到信号的时间？
提示
逐个打开提示，每个都会多透露一点。
节点在从
k到达它的最快路径所需的时间后收到信号。因此，答案是这些最快时间中的最大值；如果某个节点完全没有路径可到达，则答案为 -1。没有任何一条边的耗时是负数。因此，在时间尚未确定的节点中，暂定时间最小的节点不可能变得更快：到达它的其他路线都要经过这些节点中的另一个，而到达那个节点不会更早。按到达顺序确定节点。
维护一个由
(time, node)对组成的最小堆。弹出最小的元素，如果该节点已有更小的时间，就跳过它；将所有时间得到改善的邻居加入堆中。堆为空时，取最大的时间。
题解
每个节点收到信号的时间等于从 k 出发到该节点的最快路线长度，因此需要先求单源最短路径，再取最大值；如果某个节点无法到达，则返回 -1。链路时间始终非负，因此 Dijkstra 算法只会确定每个节点一次。下面，E 表示 times.length。
在每条更快的路径上都会重新访问的深度优先搜索
结果正确，但无法在最大的测试中运行完毕
思路
从 k 开始进行深度优先搜索，同时记录已用时间，并记录每个节点最快的到达时间。到达某个节点时，如果路线用时不比该节点的记录更短，搜索就会停止；如果用时更短，就更新记录并继续搜索。最终，每条记录都会变成真正的最快到达时间，因为最快路线总会在某个时刻更新它。
一个节点可能会被多次更新。把 18 个闸门排成一行，每对闸门之间都用一条免费通道相连，同时还有一条绕行路线，绕行时间依次为 65,536、32,768，一直到 1。如果先尝试绕行路线，搜索就会以 131,072 种不同的时间到达最后一个闸门，并且每次都会遍历它后面的所有内容：工作量相对于 n 呈指数增长。
算法
- 将每个最短时间设为无穷大，并将
(k, 0)压入栈中。 - 弹出
(node, t)。如果不满足t < best[node]，就跳过；否则设置best[node] = t。 - 对于从
node出发的每条连接，如果到达时间小于best[next]，就将(next, t + w)压入栈中。 - 栈为空时，如果有任何最短时间仍为无穷大，就返回 -1；否则返回其中的最大值。
def networkDelayTime(times, n, k):
graph = [[] for _ in range(n + 1)]
for u, v, w in times:
graph[u].append((v, w))
INF = float("inf")
best = [INF] * (n + 1) # the fastest arrival found so far at each node
stack = [(k, 0)]
while stack:
node, t = stack.pop()
# A route that is not faster than one already found adds nothing.
if t >= best[node]:
continue
best[node] = t
# Push in reverse so the first listed edge is explored first.
for nxt, w in reversed(graph[node]):
if t + w < best[nxt]:
stack.append((nxt, t + w))
worst = 0
for node in range(1, n + 1):
if best[node] == INF:
return -1
worst = max(worst, best[node])
return worstBellman-Ford：最多对每条边进行 n-1 次松弛
思路
为每个节点保留一个暂定时间 dist，将 k 的时间设为 0。松弛一条边 u → v 时，如果 dist[u] + w 更小，就将 dist[v] 更新为这个值。Bellman-Ford 会在每一轮中松弛所有边。
取一条到某个节点的最快路线，比如 k → a → b → v。第一轮会确定 dist[a]，第二轮确定 dist[b]，第三轮确定 dist[v]。最快路线不会重复经过同一个节点，因此最多有 n-1 条边，n-1 轮就能确定所有节点。
每轮的开销是 O(E)。一条按从远端到近端的顺序列出的 3,000 个节点的链，需要对 4,000 条边进行 2,999 轮松弛：约 1,200 万次松弛。
算法
- 将
dist[k] = 0，并将其他所有dist设为无穷大。 - 最多重复 n-1 次：对每条连接
[u, v, w]，如果dist[u] + w < dist[v]，就设置dist[v] = dist[u] + w。 - 如果某一轮没有任何变化，就提前停止。
- 如果仍有任何
dist为无穷大，则返回 -1；否则返回其中最大的值。
def networkDelayTime(times, n, k):
INF = float("inf")
dist = [INF] * (n + 1)
dist[k] = 0
# A fastest route visits each node at most once, so it has at most n-1 edges,
# and n-1 passes over every edge are enough to find it.
for _ in range(n - 1):
changed = False
for u, v, w in times:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
changed = True
if not changed: # a pass that improves nothing means every time is final
break
worst = 0
for node in range(1, n + 1):
if dist[node] == INF:
return -1
worst = max(worst, dist[node])
return worst使用最小堆的 Dijkstra 算法
思路
在尚未确定的节点中，暂定时间最小的节点已经是最终确定的。任何其他到达它的路径，都必须经过一个尚未确定的节点离开已确定节点，而该节点的时间至少和它一样大；之后的边只会增加时间，因为没有负数边。因此，确定这个节点，松弛它的边一次，然后重复。
最小堆可以找到时间最小的节点。当一个节点的时间变小时，推入一条新记录，并保留旧记录；弹出的记录如果时间大于 dist，就说明它已过期，因此跳过。每条边最多推入一条记录，所以堆中最多有 E + 1 条记录，总时间复杂度为 O(E log E)。
算法
- 将
dist[k] = 0，将其他所有dist设为无穷大，并将(0, k)放入最小堆。 - 取出最小的
(t, node)；如果t > dist[node]，说明它已过期，跳过。 - 对于每条从
node → next出发、耗时为w的连接，如果t + w < dist[next]，就将dist[next] = t + w，并将(t + w, next)放入堆中。 - 堆为空时，如果任何
dist都是无穷大，则返回 -1；否则返回其中的最大值。
import heapq
def networkDelayTime(times, n, k):
graph = [[] for _ in range(n + 1)]
for u, v, w in times:
graph[u].append((v, w))
INF = float("inf")
dist = [INF] * (n + 1)
dist[k] = 0
heap = [(0, k)] # (arrival time, node), smallest time on top
while heap:
t, node = heapq.heappop(heap)
# A stale entry: this node was already reached sooner.
if t > dist[node]:
continue
# t is now final: every other route reaches node later.
for nxt, w in graph[node]:
if t + w < dist[nxt]:
dist[nxt] = t + w
heapq.heappush(heap, (t + w, nxt))
worst = 0
for node in range(1, n + 1):
if dist[node] == INF:
return -1
worst = max(worst, dist[node])
return worst
易错点和边界情况
- 把链接当成双向的。
[3, 1, 2]只会把信号从节点 3 传到节点 1，因此在第二个示例中，节点 3 始终收不到信号。 - 使用普通的广度优先搜索。它会找出包含最少链接的路线：在第一个示例中，它算出的节点 2 的时间是 4，而不是 3。
- 忘记处理 -1。未经检查就取最大值会返回无穷大，或者忽略从未收到信号的节点。
- 用最大的 int 表示无穷大。对于尚未到达的
u，dist[u] + w会溢出成负数；跳过尚未到达的节点，或者使用 10^9。
常见问题3
网络延迟时间的时间复杂度是多少？
使用 Dijkstra 算法和二叉堆时，时间复杂度为 O(E log E)，其中 E 是链接的数量。由于 E 至多为 n²，因此这等于 O(E log n)。空间复杂度为 O(n + E)。Bellman-Ford 的时间复杂度为 O(n · E)。
为什么 Dijkstra 算法需要非负权重？
Dijkstra 不会重新访问已确定的节点，只有在之后不存在更短路径时，这样做才安全。对于耗时为 2 的链接 A → B、耗时为 3 的链接 A → C 和耗时为 -2 的链接 C → B，它会在距离为 2 时确定 B，但经过 C 的路径到达 B 时距离为 1。Bellman-Ford 能处理负耗时。
你能不用堆解决网络延迟时间问题吗？
是的。使用普通数组实现的 Dijkstra 会扫描每个尚未确定的节点，找出耗时最短的节点，总时间复杂度为 O(n²)。在 E 接近 n² 的稠密图中，这种方法更快。在稀疏图中，例如有 3,000 个节点和 4,000 条边时，堆版本需要做的工作少得多。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def networkDelayTime(times, n, k):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
times = [[1, 2, 4], [1, 3, 1], [3, 2, 2], [2, 4, 1]] n = 4 k = 1
预期输出
4