Network Delay Time

MediumGraphs · Shortest Path (Dijkstra)🧩 Shortest Paths LeetCode #743 ↗Updated Oct 30, 2026

Problem

A network has nodes 1..n and directed, weighted edges times[i] = [u, v, w] (a signal takes w time to go from u to v). A signal starts at node k. Return the time until every node has received it, or -1 if some node never does.

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

Input[[1,2,1]], n=2, k=1Output1

Input[[1,2,1]], n=2, k=2Output-1

1 ≤ k ≤ n ≤ 100 · 1 ≤ times.length ≤ 6000 · 0 ≤ w ≤ 100 · u ≠ v, no duplicate (u, v)

Try it yourself

Java

class Solution {
    public int networkDelayTime(int[][] times, int n, int k) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

The answer is the largest shortest-path distance from k. Weights are non-negative, so Dijkstra applies: the closest unsettled node can never be improved later.

PatternShortest Paths

Instinct Weighted edges plus "minimum cost, time or effort to reach" - grab a min-heap and always expand the cheapest unsettled node next (Dijkstra).

Memory hack Pop the cheapest, skip the stale, relax the rest - Dijkstra is a ripple in a pond that touches near shores before far ones.

Open the Shortest Paths guide →

Approaches

Brute ForceFloyd–Warshall (All Pairs)

Time O(n³)Space O(n²)

Compute shortest paths between every pair: for each intermediate node m, allow paths through it via d[i][j] = min(d[i][j], d[i][m] + d[m][j]). Then read row k. Use INF = MAX/2 so INF + INF cannot overflow.

Java

public int networkDelayTime(int[][] times, int n, int k) {
    final int INF = Integer.MAX_VALUE / 2;
    int[][] d = new int[n + 1][n + 1];
    for (int[] row : d) Arrays.fill(row, INF);
    for (int i = 1; i <= n; i++) d[i][i] = 0;
    for (int[] t : times) d[t[0]][t[1]] = t[2];
    for (int m = 1; m <= n; m++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                d[i][j] = Math.min(d[i][j], d[i][m] + d[m][j]);
    int ans = 0;
    for (int j = 1; j <= n; j++) ans = Math.max(ans, d[k][j]);
    return ans >= INF ? -1 : ans;
}

Dead simple, but solves an all-pairs problem when we need one source.

BetterBellman–Ford (Relax All Edges)

Time O(n · E)Space O(n)

A shortest path uses at most n-1 edges, so relaxing every edge n-1 times is enough to settle all distances. Stop early once a full round changes nothing.

Java

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 round = 1; round < n; round++) {
        boolean changed = false;
        for (int[] t : times)
            if (dist[t[0]] != Integer.MAX_VALUE && dist[t[0]] + t[2] < dist[t[1]]) {
                dist[t[1]] = dist[t[0]] + t[2];
                changed = true;
            }
        if (!changed) break; // already settled
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) ans = Math.max(ans, dist[i]);
    return ans == Integer.MAX_VALUE ? -1 : ans;
}

Single-source and handles negative weights, but rescans all edges each round.

OptimalDijkstra with a Min-Heap

Time O(n + E log E)Space O(n + E)

Always expand the node with the smallest known time. With non-negative weights nothing popped later can shorten it, so each node is settled once and each edge relaxed once. Skip stale heap entries whose time exceeds dist[u].

Java

public int networkDelayTime(int[][] times, int n, int k) {
    List<List<int[]>> adj = new ArrayList<>();
    for (int i = 0; i <= n; i++) adj.add(new ArrayList<>());
    for (int[] t : times) adj.get(t[0]).add(new int[]{t[1], t[2]});
    int[] dist = new int[n + 1];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[k] = 0;
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
    pq.offer(new int[]{0, k}); // {time, node}
    while (!pq.isEmpty()) {
        int[] cur = pq.poll();
        int d = cur[0], u = cur[1];
        if (d > dist[u]) continue; // stale entry
        for (int[] e : adj.get(u))
            if (d + e[1] < dist[e[0]]) {
                dist[e[0]] = d + e[1];
                pq.offer(new int[]{dist[e[0]], e[0]});
            }
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) ans = Math.max(ans, dist[i]);
    return ans == Integer.MAX_VALUE ? -1 : ans;
}

Touches each edge once plus heap cost — the standard answer.

At a glance

Level	Approach	Time	Space
Brute Force	Floyd–Warshall (All Pairs)	`O(n³)`	`O(n²)`
Better	Bellman–Ford (Relax All Edges)	`O(n · E)`	`O(n)`
Optimal	Dijkstra with a Min-Heap	`O(n + E log E)`	`O(n + E)`

Common pitfalls

Returning the sum of edge times instead of the max shortest distance.
Overflow: MAX_VALUE + w wraps negative — guard or use MAX/2.
Forgetting 1-indexed nodes — arrays need size n + 1.

Interview tips

Clarify: weights ≥ 0? Then Dijkstra; negatives ⇒ Bellman–Ford.
Explain the stale-entry skip (lazy deletion) instead of decrease-key.
Unreachable node ⇒ its distance stays ∞ ⇒ return -1.

Pattern

Dijkstra → single-source shortest paths on a graph with non-negative weights.

My notes saved in this browser