How do I approach the 'Network Delay Time' problem?

Start by choosing a graph traversal method like DFS or BFS. For more efficiency with weighted edges, use Dijkstra's algorithm with a priority queue.

What is the time complexity of this problem?

The time complexity depends on the approach: DFS/BFS is O(V + E), and Dijkstra's algorithm with a priority queue is O((V + E) log V).

Can I use BFS for graphs with different edge weights?

BFS works best for graphs with uniform edge weights. For non-uniform weights, Dijkstra's algorithm is more efficient.

How do I handle unreachable nodes in 'Network Delay Time'?

Make sure to check for nodes that remain unvisited after the traversal and return -1 if not all nodes can receive the signal.

What makes DFS unsuitable for large networks in this problem?

DFS can be inefficient for large networks, especially when dealing with cycles or non-uniform edge weights. Dijkstra's algorithm with a priority queue offers better performance for such cases.

#743

Medium

auto_awesome图·DFS·traversal

LeetCode 题解工作台

网络延迟时间

有 n 个网络节点，标记为 1 到 n 。给你一个列表 times ，表示信号经过有向边的传递时间。 times[i] = (u i , v i , w i ) ，其中 u i 是源节点， v i 是目标节点， w i 是一个信号从源节点传递到目标节点的时间。现在，从某个节点 K 发出一个信…

深度优先搜索广度优先搜索图堆（优先队列）最短路径

题目描述

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

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

现在，从某个节点 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 <= u_i, v_i <= n
u_i != v_i
0 <= w_i <= 100
所有 (u_i, v_i) 对都 互不相同（即，不含重复边）

lightbulb

解题思路

方法一：朴素 Dijkstra 算法

我们定义 $\textit{g}[u][v]$ 表示节点 $u$ 到节点 $v$ 的边权，如果节点 $u$ 到节点 $v$ 之间没有边，则 $\textit{g}[u][v] = +\infty$ 。

我们维护一个数组 $\textit{dist}$ ，其中 $\textit{dist}[i]$ 表示节点 $k$ 到节点 $i$ 的最短路径长度。初始时，我们将 $\textit{dist}[i]$ 全部初始化为 $+\infty$ ，但 $\textit{dist}[k - 1] = 0$ 。定义一个数组 $\textit{vis}$ ，其中 $\textit{vis}[i]$ 表示节点 $i$ 是否被访问过，初始时，我们将 $\textit{vis}[i]$ 全部初始化为 $\text{false}$ 。

我们每次找到未被访问的距离最小的节点 $t$ ，然后以节点 $t$ 为中心进行松弛操作，即对于每个节点 $j$ ，如果 $\textit{dist}[j] > \textit{dist}[t] + \textit{g}[t][j]$ ，则更新 $\textit{dist}[j] = \textit{dist}[t] + \textit{g}[t][j]$ 。

最后，我们返回 $\textit{dist}$ 中的最大值，即为答案。如果答案为 $+\infty$ ，则说明存在无法到达的节点，返回 $-1$ 。

时间复杂度 $O(n^2 + m)$ ，空间复杂度 $O(n^2)$ 。其中 $n$ 和 $m$ 分别为节点数和边数。

class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        g = [[inf] * n for _ in range(n)]
        for u, v, w in times:
            g[u - 1][v - 1] = w
        dist = [inf] * n
        dist[k - 1] = 0
        vis = [False] * n
        for _ in range(n):
            t = -1
            for j in range(n):
                if not vis[j] and (t == -1 or dist[t] > dist[j]):
                    t = j
            vis[t] = True
            for j in range(n):
                dist[j] = min(dist[j], dist[t] + g[t][j])
        ans = max(dist)
        return -1 if ans == inf else ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
The candidate is expected to demonstrate knowledge of graph traversal methods and the ability to optimize with a priority queue or BFS.
question_mark
Be prepared for candidates to compare DFS and BFS as options, with an emphasis on using the most efficient method for large input sizes.
question_mark
A successful answer should include handling edge cases, such as unreachable nodes or cycles, and the reasoning for selecting the approach used.

warning

常见陷阱

外企场景

error
Failing to correctly handle the case where not all nodes can receive the signal, leading to an incorrect return value of -1.
error
Incorrectly assuming all graphs are uniform, which may lead to inefficient solutions or improper use of BFS/Dijkstra.
error
Not accounting for the possibility of cycles in the graph, which could lead to an infinite loop or incorrect time calculations.

swap_horiz

进阶变体

外企场景

arrow_right_alt
A variation of this problem could involve multiple source nodes for the signal, testing the candidate's ability to modify their approach to handle additional starting points.
arrow_right_alt
Another variant could involve a directed graph with negative edge weights, which would require considering algorithms like Bellman-Ford instead of Dijkstra or BFS.
arrow_right_alt
The problem could also be modified by adding additional constraints, such as limiting the number of allowed edges, which could test the candidate's ability to optimize graph traversal techniques.

help

常见问题

外企场景

继续练习

#787 K 站中转内最便宜的航班 #399 除法求值 #1368 使网格图至少有一条有效路径的最小代价