Network Delay Time

medium

Find time for all nodes to receive signal from source

Network Delay Time

Key Insight

This is weighted shortest path from one source: repeatedly finalize the nearest unreached node and relax its outgoing edges.

Step 1Initialize Distances
dist[source=1] = 0Others unknown
0
0
∞
1
∞
2
∞
3
∞
4

Start with source distance 0 and others as infinity.

1 / 3

Learn the Pattern

SortingUse sorting as a preprocessing step to simplify problems, or apply partition logic for in-place rearrangement. Many interview problems become trivial once the array is sorted.
HeapUse a heap (priority queue) when you repeatedly need the minimum or maximum of a changing set while also inserting and deleting values efficiently.
Practice the Code

Step-by-Step Walkthrough: Network Delay Time

This is weighted shortest path from one source: repeatedly finalize the nearest unreached node and relax its outgoing edges.

  1. Initialize Distances

    Start with source distance 0 and others as infinity.

  2. Relax Edges from Closest Node

    Pick current closest unreached node and update neighbors if we can improve their distances.

  3. Finish with Minimum Total Time

    After all reachable nodes are finalized, the answer is the maximum of finite distances.