← DSA Atlas
Dedicated problem page · #743

Network Delay Time

MediumShortest Path, Dijkstra and Minimum Spanning TreeSingle-source shortest pathDijkstra with a min-heap
Solve on LeetCode ↗
743
MediumShortest Path, Dijkstra and Minimum Spanning TreeDijkstra with a min-heapSingle-source shortest path

Network Delay Time

You are given a directed weighted graph of n nodes labeled 1..n and a list times where times[i] = (u, v, w) means a signal takes w time to travel from node u to node v. A signal starts at node k. Return the minimum time for all n nodes to receive the signal, or -1 if some node can never receive it.

Open official problem prompt ↗
In plain English

Find how long it takes for a signal broadcast from node k to reach the farthest node, i.e. the longest of all shortest paths from k.

Picture it like this

Like ripples spreading from a stone dropped in a pond: the whole surface is 'covered' only when the ripple reaches the most distant edge.

Example
Input
times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
Output
2
Why
From node 2 the signal reaches 1 in time 1, 3 in time 1, and 4 via 3 in time 2; the slowest arrival is 2.
Constraints
1 <= k <= n <= 1001 <= times.length <= 6000times[i] = (u_i, v_i, w_i)1 <= u_i, v_i <= nu_i != v_i0 <= w_i <= 100All (u_i, v_i) pairs are unique
Pattern lesson

See the pattern, then code

Single-source shortest path
Recognition clue

Shortest travel time from a single source in a graph with non-negative edge weights is the textbook signal for Dijkstra.

↗
Shortest Path, Dijkstra and Minimum Spanning Tree

Shortest paths with non-negative weights or minimum-cost graph connection.. The answer is the maximum of the shortest distances from k to every node. Dijkstra settles nodes in increasing distance, so the first time we pop a node its distance is final.

New words, made simpleKnow these before the algorithm
Relaxation
Trying to improve a node's best-known distance using an edge into it.
Settled node
A node whose shortest distance is finalized and will never change.
Min-heap (priority queue)
A structure that always hands back the smallest pending distance next.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Repeated Bellman-Ford relaxation

Correct but slower; unnecessary since all weights are non-negative.

Relax all edges n-1 times to propagate distances.

Time O(V*E)Space O(V)
Best choiceDijkstra with a min-heap

Optimal for non-negative weights; each node is finalized exactly once.

Greedily settle the closest unsettled node and relax its outgoing edges.

Time O(E log V)Space O(V + E)
The rule we keep true

Invariant

When a node is popped from the heap for the first time, the distance recorded for it is its true shortest distance from k.

Why this is correct

Reasoning

With non-negative weights, any later path to an already-popped node must go through the heap with a distance at least as large, so the first pop is optimal. Once every node is settled, the maximum settled distance is the time for full coverage.

The algorithm in three movesSay these aloud before coding
1Build an adjacency list from times

pq=[(0,2)] -> settle 2 at 0

2Push (0, k) into a min-heap and pop the closest unsettled node

relax: push (1,1),(1,3)

3Skip already-settled nodes; otherwise fix its distance and relax its neighbors

settle 1@1, 3@1, then 4@2 -> answer max=2

4After the heap empties, return the max distance if all n nodes were reached, else -1

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
k=20
11
32
43
1 · Readsource k=2
2 · AskWhich node is closest?
3 · Update statepq=[(0,2)], dist={}
4 · ResultPop (0,2), settle dist[2]=0
Key takeaway

Signal spreads from source node 2; labels show final shortest arrival times.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 3-5Build adjacency list

    Group outgoing edges (v, w) by their source u for O(1) neighbor lookup.

  2. 2
    Lines 6-8Init heap and dist map

    dist stores only settled nodes; start with source at distance 0.

  3. 3
    Lines 9-13Pop and settle

    Skip if already settled (lazy deletion), otherwise fix the distance.

  4. 4
    Lines 14-16Relax neighbors

    Push improved candidate distances for unsettled neighbors.

  5. 5
    Lines 17Final answer

    Return max distance if all n nodes settled, else -1.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • A node unreachable from k -> return -1
  • n == 1 (source only) -> answer 0
  • Zero-weight edges are allowed
  • Multiple nodes at the same distance
!

Common beginner mistakes

  • Forgetting the lazy-deletion check lets stale heap entries corrupt results or waste work
  • Comparing len(dist) against n to detect unreachable nodes is required; a plain max is wrong
  • Using nodes indexed 1..n but sizing arrays for 0..n-1
Check your understanding

Why can we return a node's distance the moment it is first popped, instead of waiting?

More in Shortest Path, Dijkstra and Minimum Spanning Tree

#332Reconstruct ItineraryEulerian path (Hierholzer's algorithm)#505The Maze IIWeighted shortest path on a grid#778Swim in Rising WaterMinimize the maximum along a path (minimax path)#787Cheapest Flights Within K StopsShortest path with a hop limit#815Bus RoutesUnweighted shortest path (fewest transfers)#1135Connecting Cities With Minimum CostMinimum spanning tree (Kruskal)