LeetCode · #743

Network Delay Time Solution

Given a weighted directed graph of network nodes, find the minimum time for a signal sent from node k to reach all nodes — or return -1 if impossible.

Section One · Problem

Problem Statement

🏷️

Difficulty

Medium

🔗

LeetCode

Problem #743

🏗️

Pattern

Graph — Dijkstra shortest path

You have a network of n nodes labeled 1 to n and a list of travel times times[i] = [u, v, w] (directed edge u→v with weight w). Given source node k, return the minimum time for all n nodes to receive the signal, or -1 if any node is unreachable.

Example

 Input: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2 Output: 2 // 2→1 costs 1, 2→3 costs 1, 3→4 costs 2. Slowest = node 4 at time 2. 

Constraints

 • 1 ≤ k ≤ n ≤ 100 • 1 ≤ times.length ≤ 6000  ← dense graph possible; Dijkstra with heap O((V+E) log V) • All edge weights are positive  ← key: no negative weights → Dijkstra works 

Section Two · Approach 1

Bellman-Ford — O(V · E)

Initialize all distances to infinity except dist[k] = 0. Relax all edges V-1 times. After each pass, if any distance improved, carry it forward. The final dist array holds the shortest path from k to every node. Return the maximum if all are reachable.

Why it works

Bellman-Ford correctly handles any graph without negative cycles. After V-1 iterations, all shortest paths of at most V-1 edges are found. Since all weights are positive here, it converges correctly.

Why we can do better

Problem: Bellman-Ford runs V−1 passes over all E edges: O(V · E). For this problem V=100 and E=6000, that's 600,000 operations — acceptable, but Dijkstra processes each node once and uses a min-heap to greedily expand the shortest known distance first, giving O((V+E) log V) ≈ 6,700 operations. More importantly, Dijkstra is the canonical algorithm to know for any non-negative weighted single-source shortest paths problem.

Java — Bellman-Ford

 import java.util.*;
class Solution {
public int networkDelayTime(int[][] times, int n, int k) {
int[] dist = new int[n + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[k] = 0;
for (int i = 0; i < n - 1; i++) { // V-1 passes for (int[] t : times) {
int u=t[0], v=t[1], w=t[2];
if (dist[u] != Integer.MAX_VALUE &&
                    dist[u] + w < dist[v])
                    dist[v] = dist[u] + w;
            }
        }
int ans = 0;
for (int i = 1; i <= n; i++) {
if (dist[i] == Integer.MAX_VALUE) return -1;
            ans = Math.max(ans, dist[i]);
        }
return ans;
    }
}

Python — Bellman-Ford

 class Solution:
def networkDelayTime(self, times: list[list[int]], n: int, k: int) -> int:
        dist = [float('inf')] * (n + 1)
        dist[k] = 0 for _ in range(n - 1): # V-1 passes for u, v, w in times:
if dist[u] + w < dist[v]:
                    dist[v] = dist[u] + w
        ans = max(dist[1:])
return ans if ans < float('inf') else -1 

Metric	Value
Time	O(V · E) — V-1 passes over E edges
Space	O(V) — distance array

Section Three · Approach 2

Dijkstra — O((V+E) log V)

Use a min-heap (priority queue) keyed by cumulative distance. Always expand the node with the current shortest known distance. Since all weights are positive, once a node is popped from the heap, its shortest path is finalized.

💡 Mental model: Imagine a radio signal spreading outward from a transmitter. The signal always travels along the shortest available path first — it's greedy. You track a "wavefront" (the priority queue) of all known, unconfirmed arrivals. Each time the fastest signal arrives at a new relay tower (node), you record its arrival time (finalized distance) and propagate onward to its neighbors. You never revisit a tower whose signal has already been confirmed, because no shorter path could arrive later (all edges are positive).

Algorithm — Dijkstra with min-heap

Build adjacency list: adj[u] = [(v, w), ...].
Initialize dist[k] = 0, all others ∞. Push (0, k) to min-heap.
Pop (d, u) with smallest d. If d > dist[u], skip (stale entry).
For each neighbor (v, w): if dist[u] + w < dist[v], update and push to heap.
After heap is empty: return max(dist[1..n]), or -1 if any is still ∞.

🎯 When to recognize this pattern:

"Shortest path from a single source, non-negative weights." Dijkstra is the go-to for: network latency (this problem), LC 1514 (Path With Maximum Probability — negate logs), LC 1631 (Path with Minimum Effort), LC 787 (Cheapest Flights Within K Stops — modified Dijkstra).
If weights can be negative, use Bellman-Ford. If you need all-pairs shortest paths, use Floyd-Warshall.

Why the "stale entry" skip works:

Java's PriorityQueue doesn't support decrease-key, so we push duplicate entries instead.
An entry (d, u) is stale if d > dist[u] — meaning we already found a shorter path to u and processed it.
Skipping stale entries is O(1) and correct: the first time u is popped is always with its true shortest distance.

Section Four · Trace

Visual Walkthrough

Trace Dijkstra from k=2 on times=[[2,1,1],[2,3,1],[3,4,1]], n=4.

Dijkstra — Network Delay Time (source k=2)

Section Five · Implementation

Code — Java & Python

Java — Dijkstra with min-heap

 import java.util.*;
class Solution {
public int networkDelayTime(int[][] times, int n, int k) {
List<int[]>[] adj = new List[n + 1];
for (int i = 0; i <= n; i++) adj[i] = new ArrayList<>();
for (int[] t : times) adj[t[0]].add(new int[]{t[1], t[2]});
int[] dist = new int[n + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[k] = 0;
// [distance, node] — min-heap by distance PriorityQueue<int[]> pq = new PriorityQueue<>((a,b) -> a[0]-b[0]);
        pq.offer(new int[]{0, k});
while (!pq.isEmpty()) {
int[] curr = pq.poll();
int d = curr[0], u = curr[1];
if (d > dist[u]) continue; // stale entry — skip for (int[] nb : adj[u]) {
int v = nb[0], w = nb[1];
if (dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    pq.offer(new int[]{dist[v], v});
                }
            }
        }
int ans = 0;
for (int i = 1; i <= n; i++) {
if (dist[i] == Integer.MAX_VALUE) return -1; // unreachable node
ans = Math.max(ans, dist[i]);
        }
return ans; // slowest arrival = answer
}
}

Python — Dijkstra with heapq

 import heapq
class Solution:
def networkDelayTime(self, times: list[list[int]], n: int, k: int) -> int:
        adj = [[] for _ in range(n + 1)]
for u, v, w in times:
            adj[u].append((v, w))

        dist = [float('inf')] * (n + 1)
        dist[k] = 0
heap = [(0, k)] # (distance, node) while heap:
            d, u = heapq.heappop(heap)
if d > dist[u]:
continue # stale entry for v, w in adj[u]:
                nd = dist[u] + w
if nd < dist[v]:
                    dist[v] = nd
                    heapq.heappush(heap, (nd, v))

        ans = max(dist[1:])
return ans if ans < float('inf') else -1 

Section Six · Analysis

Complexity Analysis

Approach	Time	Space	Trade-off
Bellman-Ford	O(V · E)	O(V)	Handles negative weights; simpler to implement; slower
Floyd-Warshall	O(V³)	O(V²)	All-pairs shortest paths; overkill for single source
Dijkstra ← optimal	O((V+E) log V)	O(V + E)	Fastest for non-negative weights; standard in interviews

Why Dijkstra fails with negative weights:

Dijkstra assumes that once a node is popped from the heap, its distance is final.
With negative edges, a later path could update an already-finalized node to a smaller distance — violating the greedy assumption.
Use Bellman-Ford or SPFA when negative edges exist.

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Input	Why It Matters
Unreachable node	Graph is disconnected	Some `dist[i]` stays `∞`. Return `-1`.
Single node	`n=1, times=[], k=1`	No edges. `dist[1]=0`. max = 0 → return 0.
Multiple paths to same node	Two routes with different weights	Dijkstra always takes the shorter path first. dist[] is updated correctly.
Zero-weight edge	`w=0` on some edge	Dijkstra handles `w=0` correctly — effectively "instantaneous" relay.
Large weights causing overflow	Weights near Integer.MAX_VALUE/2	dist[u] + w could overflow int if dist[u] is MAX_VALUE. Guard with `dist[u] != MAX_VALUE` check before adding.
Stale heap entries	Node updated multiple times	The heap may contain multiple `(d, u)` pairs. The `d > dist[u]` check correctly skips outdated entries.

⚠ Common Mistake: Not including the stale-entry check (if (d > dist[u]) continue). Without it, a node can be "finalized" multiple times when stale (higher) distances are later popped from the heap. While the answer won't be wrong (dist[] is already correct), the algorithm processes neighbors again unnecessarily, potentially adding more stale entries and blowing up runtime for dense graphs. Always skip stale entries.

← Back to Graph problems

LearningTree

LC 743 · Network Delay Time — Solution & Explanation | DSA Guide