Coding interview problems › Graphs & Grids

🗺️ Graphs & Grids Medium

Network Delay Time

Network Delay Time explained: Dijkstra's algorithm with a min-heap finds when the signal reaches the last node. Tested Python code, pitfalls and a live visual.

Also searched as: Dijkstra's algorithm example problem ¡ single-source shortest path with a heap

🧭

Try it live Free

Dijkstra's Shortest Path

Step through the Dijkstra lab and watch it always settle the nearest unsettled node and relax its edges; the last node settled is when the signal reaches everyone.

Also useful: Binary Heap & Priority Queue

Open the playground →

The problem

A network has n nodes and directed edges (u, v, w): a signal takes time w to travel from u to v. A signal starts at node k. Return how long until every node has received it, or -1 if some node never does.

Inputtimes = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
Output2

Node 4 is reached last, at time 2.

The key insight

Each node receives the signal at its shortest-path distance from k, so the answer is the largest of those distances. With non-negative weights, Dijkstra's algorithm computes them all: always settle the closest unsettled node from a min-heap, then relax its outgoing edges.

Brute force first: Bellman-Ford (relax every edge n - 1 times) also works, in O(V¡E), and handles negative weights that this problem does not have.

Step-by-step approach

  1. Build an adjacency list u -> [(v, w)].
  2. Push (0, k) onto a min-heap; keep a dist map of settled nodes.
  3. Pop the smallest (d, u). If u is already settled, skip it; otherwise settle it with distance d.
  4. For each edge (v, w) from u where v is unsettled, push (d + w, v).
  5. If all n nodes are settled, return the maximum distance; else return -1.

Python solution

PYTHON 3tested
import heapq
from collections import defaultdict


def network_delay_time(times, n, k):
    graph = defaultdict(list)
    for u, v, w in times:
        graph[u].append((v, w))
    dist = {}                          # settled node -> shortest time
    heap = [(0, k)]
    while heap:
        d, u = heapq.heappop(heap)
        if u in dist:
            continue                   # stale entry: already settled cheaper
        dist[u] = d
        for v, w in graph[u]:
            if v not in dist:
                heapq.heappush(heap, (d + w, v))
    return max(dist.values()) if len(dist) == n else -1

Complexity

TimeO(E log E)
SpaceO(V + E)

Every edge can push one heap entry, and each push or pop costs O(log E). The graph, the heap and the distance map are linear in V + E.

Common mistakes

Frequently asked questions

What is the time and space complexity of Network Delay Time?

With Dijkstra and a binary heap it is O(E log E) time, which is the same as O(E log V), and O(V + E) space for the graph, heap and distances.

Why does Dijkstra fail with negative edge weights?

It assumes a settled node's distance can never improve. A negative edge discovered later could make a shorter path to an already settled node, breaking that assumption. Use Bellman-Ford instead.

Why is the answer the maximum distance?

The signal travels along all paths at once, so each node hears it at its shortest-path time. Everyone has received it once the slowest of those times has passed.

Preparing for placements?

Take the 2-minute readiness check to find your weak patterns, then follow the placement path from DSA core to system design.

📋 2-minute readiness check The full placement path

All coding interview problems More Graphs & Grids Graph Search: BFS vs DFS lab Placement prep guides

Problem statements on this site are written in our own words. Problem names are the common names used across interview-prep communities; BitBootcamp is an independent learning platform and is not affiliated with LeetCode or any company that asks these questions.