Problem

You are given a network of n nodes, labeled from 1 to n. You are also given times, a list of travel times as directed edges times[i] = (uᵢ, vᵢ, wᵢ), where uᵢ is the source node, vᵢ is the target node, and wᵢ is the time it takes for a signal to travel from source to target.

We will send a signal from a given node k. Return the minimum time it takes for all the n nodes to receive the signal. If it is impossible for all the n nodes to receive the signal, return -1.

https://leetcode.cn/problems/network-delay-time/

Example 1:

case1

Input: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
Output: 2

Example 2:

Input: times = [[1,2,1]], n = 2, k = 1
Output: 1

Example 3:

Input: times = [[1,2,1]], n = 2, k = 2
Output: -1

Constraints:

  • 1 <= k <= n <= 100
  • 1 <= times.length <= 6000
  • times[i].length == 3
  • 1 <= uᵢ, vᵢ <= n
  • uᵢ != vᵢ
  • 0 <= wi <= 100
  • All the pairs (uᵢ, vᵢ) are unique. (i.e., no multiple edges.)

Test Cases

1
2
class Solution:
def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
solution_test.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
import pytest

from solution import Solution


@pytest.mark.parametrize('times, n, k, expected', [
([[2,1,1],[2,3,1],[3,4,1]], 4, 2, 2),
([[1,2,1]], 2, 1, 1),
([[1,2,1]], 2, 2, -1),
])
class Test:
def test_solution(self, times, n, k, expected):
sol = Solution()
assert sol.networkDelayTime(times, n, k) == expected

Thoughts

记信号传输到节点 i 所需的最小时间为 c(i)。初始时 c(k) = 0,其他均为

从节点 k 出发遍历图。如果信号从 u 传播到 v,易知 c(v) = min{c(v), c(u) + w(u, v)}。如果 c(v) 被更新(发现了能更快传播到 v 的路径),继续递归处理 v 的下游节点。

使用广度优先遍历有可能得到更多的剪枝,广度优先可以用队列。尤其如果使用带优先级的队列,每次处理信号最早到达的节点,能加大剪枝的概率。最小堆是很适合的数据结构,堆顶就是最快到达的节点,每次把堆顶推出。

做完 2290. Minimum Obstacle Removal to Reach Corner 发现其实就是实现了 Dijkstra 算法(基于优先队列优化的)。

时间复杂度 O((e + n) log n)(每个节点进入队列时要恢复堆的结构),空间复杂度 O(n)(队列大小)。e 是边的数量,即 times 数组的长度。

Code

这里直接借助 Python 自带的 heapq 辅助堆的操作。

solution.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
from heapq import heappop, heappush


class Solution:
def networkDelayTime(self, times: list[list[int]], n: int, k: int) -> int:
# adjacencies[u]: list of (v, w).
adjacencies: list[list[tuple[int, int]]] = [[] for _ in range(n)]
for u, v, w in times:
adjacencies[u-1].append((v-1, w))

costs = [-1] * n
costs[k-1] = 0
queue = [(0, k-1)]
while queue:
c_u, u = heappop(queue)
if c_u > costs[u]: # Pruning.
continue

for v, w in adjacencies[u]:
if (c_v := costs[u] + w) < costs[v] or costs[v] == -1:
costs[v] = c_v
heappush(queue, (c_v, v))

max_cost = -1
for c in costs:
if c == -1:
return -1
elif c > max_cost:
max_cost = c

return max_cost