95.Network Delay Time

MediumGraphs · 16/19

Problem

There is a network of n nodes labelled 1 to n. You are given times, where times[i] = [u, v, w] means a signal travels along a directed edge from u to v in w time units.

A signal is sent from node k. Return the minimum time it takes for all n nodes to receive it. If some node can never receive the signal, return -1.

Examples

Input:  times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
Output: 2
Explanation: Node 1 and 3 receive at t=1, node 4 receives at t=2 via 2 -> 3 -> 4.

Input:  times = [[1,2,1]], n = 2, k = 1
Output: 1

Input:  times = [[1,2,1]], n = 2, k = 2
Output: -1
Explanation: Edges are directed; node 2 cannot reach node 1.

Constraints

1 <= k <= n <= 100
1 <= times.length <= 6000
times[i].length == 3
1 <= u, v <= n, u != v
0 <= w <= 100
All pairs (u, v) are unique (no multi-edges).

💡 Key Insight

Each node receives the signal at its shortest-path distance from k, and the whole network is done when the farthest node receives it. So the answer is max(dist[v]) over all nodes, or -1 if any distance is infinite. Since all weights are non-negative, Dijkstra's algorithm computes single-source shortest paths in O(E log V).

Floyd-Warshall

TimeO(n³)SpaceO(n²)

Intuition

Compute shortest paths between every pair of nodes with dynamic programming: dist[i][j] is improved by allowing paths that pass through intermediate node m, for each m in turn. Then read the row for k. It is overkill (we only need one source) but very simple.

Algorithm

dist[i][j] = INF, dist[i][i] = 0, and dist[u][v] = w for each edge.
For m in 1..n, for i, for j: dist[i][j] = min(dist[i][j], dist[i][m] + dist[m][j]).
Answer = max(dist[k][v]); if it is INF, return -1.

Visualization

times = [[2,1,1],[2,3,1],[3,4,1]], k = 2

row k=2 initially: [1:1, 2:0, 3:1, 4:INF]
via m=3: dist[2][4] = dist[2][3] + dist[3][4] = 1 + 1 = 2
row k=2 final:     [1:1, 2:0, 3:1, 4:2]  -> max = 2

Code

java

class Solution {
    public int networkDelayTime(int[][] times, int n, int k) {
        final int INF = Integer.MAX_VALUE / 2; // halved to avoid overflow on addition
        int[][] dist = new int[n + 1][n + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                dist[i][j] = (i == j) ? 0 : INF;
            }
        }
        for (int[] t : times) {
            dist[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++) {
                    if (dist[i][m] + dist[m][j] < dist[i][j]) {
                        dist[i][j] = dist[i][m] + dist[m][j];
                    }
                }
            }
        }
        int answer = 0;
        for (int v = 1; v <= n; v++) {
            answer = Math.max(answer, dist[k][v]);
        }
        return answer >= INF ? -1 : answer;
    }
}

Complexity

Time: O(n³) — three nested loops over nodes (10⁶ for n = 100).
Space: O(n²) — the distance matrix.

Bellman-Ford

TimeO(V · E)SpaceO(V)

Intuition

A shortest path uses at most n - 1 edges. Relaxing every edge n - 1 times propagates correct distances one hop further each round. We can stop early if a full round changes nothing.

Algorithm

dist[] = INF, dist[k] = 0.
Repeat up to n - 1 times: for each edge (u, v, w), if dist[u] + w < dist[v], update dist[v]. Break if no update happened.
Answer = max of dist[1..n], or -1 if any is INF.

Visualization

edges: 2->1 (1), 2->3 (1), 3->4 (1); k = 2
           1    2    3    4
start     INF   0   INF  INF
round 1    1    0    1    2     (3->4 relaxed after 2->3 in the same pass)
round 2    1    0    1    2     no change -> stop
max = 2

Code

java

import java.util.Arrays;

class Solution {
    public int networkDelayTime(int[][] times, int n, int k) {
        final int INF = Integer.MAX_VALUE;
        int[] dist = new int[n + 1];
        Arrays.fill(dist, INF);
        dist[k] = 0;

        for (int round = 1; round < n; round++) {
            boolean changed = false;
            for (int[] t : times) {
                int u = t[0], v = t[1], w = t[2];
                if (dist[u] != INF && dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    changed = true;
                }
            }
            if (!changed) {
                break; // distances have converged
            }
        }

        int answer = 0;
        for (int v = 1; v <= n; v++) {
            if (dist[v] == INF) {
                return -1; // unreachable node
            }
            answer = Math.max(answer, dist[v]);
        }
        return answer;
    }
}

Complexity

Time: O(V · E) — up to n - 1 passes over all edges.
Space: O(V) — the distance array.

Dijkstra's AlgorithmOptimal

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

Intuition

With non-negative weights, the unvisited node with the smallest tentative distance is already final — no later path can be shorter. A min-heap pops nodes in order of distance; each popped node relaxes its outgoing edges. The last node to be finalised has the largest distance, which is our answer.

Algorithm

Build adj[u] = list of (v, w).
dist[] = INF; push (0, k) onto a min-heap.
Pop (d, u); skip if d > dist[u] is stale, or if u already finalised. Otherwise for each (v, w), if d + w < dist[v], update and push.
If any dist[v] is still INF, return -1; else return max(dist).

Dry Run

flowchart LR
    N2["2 (source)<br/>dist 0"] -->|"1"| N1["1<br/>dist 1"]
    N2 -->|"1"| N3["3<br/>dist 1"]
    N3 -->|"1"| N4["4<br/>dist 2"]

heap: (0,2)
pop (0,2): relax 1 -> 1, 3 -> 1        heap: (1,1) (1,3)
pop (1,1): no outgoing edges           heap: (1,3)
pop (1,3): relax 4 -> 2                heap: (2,4)
pop (2,4): done
dist = [1:1, 2:0, 3:1, 4:2]  -> answer 2

Code

java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;

class Solution {
    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;
        // heap of {distance, node}
        PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
        heap.offer(new int[] {0, k});

        while (!heap.isEmpty()) {
            int[] top = heap.poll();
            int d = top[0], u = top[1];
            if (d > dist[u]) {
                continue; // stale entry: a shorter path was already found
            }
            for (int[] edge : adj.get(u)) {
                int v = edge[0], nd = d + edge[1];
                if (nd < dist[v]) {
                    dist[v] = nd;
                    heap.offer(new int[] {nd, v});
                }
            }
        }

        int answer = 0;
        for (int v = 1; v <= n; v++) {
            if (dist[v] == Integer.MAX_VALUE) {
                return -1;
            }
            answer = Math.max(answer, dist[v]);
        }
        return answer;
    }
}

Complexity

Time: O(E log V) — each edge can push one heap entry; heap operations are logarithmic.
Space: O(V + E) — adjacency list, distance array and heap.

Complexity Comparison

Approach	Time	Space
Floyd-Warshall	O(V³)	O(V²)
Bellman-Ford	O(V · E)	O(V)
Dijkstra's Algorithm	O(E log V)	O(V + E)

Common Pitfalls

Treating the graph as undirected — edges only go from u to v.
Nodes are 1-indexed; allocate n + 1 slots and ignore index 0 when taking the max.
Returning the sum of distances instead of the maximum.
Adding to Integer.MAX_VALUE (overflow) — guard with dist[u] != INF or use a halved INF.
Not skipping stale heap entries, which makes Dijkstra re-relax edges from outdated distances.