Network Delay Time

Free with account Updated Nov 19, 2026 · 6 min read
On this page

    Problem statement

    A network has n nodes labeled 1 to n and directed links (u, v, w): a signal sent from u reaches v after w time units. A signal starts at node k at time 0. Return the time when every node has received it, or −1 if some node never does. Delays are non-negative.

    This is single-source shortest paths in disguise: each node hears the signal at its shortest-path time from k, and the answer is the largest of those. It is the standard way interviewers check that you know Dijkstra's algorithm and why BFS is not enough. Original problem: LeetCode 743.

    Example

    Node 1 sends at time 0; the slowest node to hear it is node 5, at time 6.
    Node 1 sends at time 0; the slowest node to hear it is node 5, at time 6.
    times = [[1,2,4], [1,3,1], [3,2,2], [2,4,1], [3,5,7], [4,5,2]], n = 5, k = 1
    Output: 6
    # node 3 at 1, node 2 at 3 (via 3), node 4 at 4, node 5 at 6 (via 2 and 4)
    Same links, n = 6, k = 1
    Output: -1        # node 6 has no incoming link

    Constraints (assumed)

    • 1 ≤ n ≤ 100; up to 6,000 links; 0 ≤ w ≤ 100.

    What this question tests

    • Recognizing single-source shortest paths with non-negative weights.
    • Implementing Dijkstra with a min-heap, including stale heap entries.
    • Turning "when does everyone hear it" into max of the shortest distances, and handling unreachable nodes.

    Questions to ask first

    1. Can delays be negative? (Here: no. With negatives you'd need Bellman-Ford.)
    2. Are links one-way? (Here: yes, directed.)
    3. Can there be several links between the same pair, or self-loops? (Yes; the algorithm handles both.)
    4. What if some node is unreachable? (Return −1.)