☕ DSA Java Articles

Topics › Graphs › Shortest Path Algorithms and Problems

Network Delay Time

Medium TUF ID 764 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

A network has n nodes labelled 1 to n. You are given times, a list of directed edges [u, v, w] meaning a signal sent from u reaches v after w units of time. A signal is sent from node k. Return the minimum time it takes for all n nodes to receive it, or -1 if some node never does.

Constraints (LeetCode 743): 1 ≤ k ≤ n ≤ 100, 1 ≤ times.length ≤ 6000, 0 ≤ w ≤ 100, and no pair (u, v) appears twice.

Example 1

times = [[2,1,1], [2,3,1], [3,4,1]], n = 4, k = 2
answer = 2          // node 1 at time 1, node 3 at time 1, node 4 at time 2

Example 2

times = [[1,2,1]], n = 2, k = 2
answer = -1         // edges are one-way, so node 1 never hears from node 2

The signal spreads along every edge at once, so each node receives it at the earliest possible moment, which is its shortest-path distance from k. The whole network is informed when the last node is, so the answer is the largest of those distances. The problem is therefore “single-source shortest paths, then take the maximum”, with -1 if any distance is infinite.

Approach 1: Brute force with Bellman-Ford

Intuition. The simplest correct shortest-path method is to keep relaxing edges until nothing improves. Relaxing edge u → v means: if reaching u and then taking the edge beats the best known time for v, record the better time. A shortest path to any node uses at most n - 1 edges, and each full pass over the edge list extends every correct prefix by at least one more edge. So n - 1 passes are enough. We also stop early if a pass changes nothing, because the next pass would see exactly the same values.

Algorithm.

  1. dist[k] = 0, every other node infinity.
  2. Repeat up to n - 1 times: for each edge [u, v, w], if dist[u] is finite and dist[u] + w < dist[v], set dist[v] = dist[u] + w. Stop early if no edge improved anything.
  3. Return the largest dist[v] for v = 1..n, or -1 if any is still infinite.
static int bellmanFord(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) {
            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;
                changed = true;
            }
        }
        if (!changed) break;                         // nothing moved, so nothing will move later
    }
    return slowest(dist, n);
}

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

Complexity. Time O(n · E): up to n - 1 passes over all E edges. Space O(n) for the distance array. With n = 100 and E = 6000 that is at most about 600,000 relaxations, which is fine for this problem, but the bound grows quickly on larger graphs. Bellman-Ford’s real strength is negative edge weights, which this problem does not have.

Approach 2: Optimal, Dijkstra with a min-heap

Intuition. With non-negative weights we can be smarter about the order of relaxation. Among all nodes not yet settled, the one with the smallest tentative time cannot be improved later. Any other route to it would have to leave the settled region through some node whose time is already at least as large, and the remaining edges add a non-negative amount. So we settle nodes in increasing order of time, using a min-heap to find the next one quickly, and relax each node’s outgoing edges exactly once.

The heap may hold several entries for the same node, because we push a new entry every time its time improves rather than decreasing a key in place. When an entry comes out with a time larger than the current dist[u], it is stale and is skipped.

Algorithm.

  1. Build an adjacency list from times. Set dist[k] = 0, push {0, k}.
  2. Pop the smallest {d, u}. If d > dist[u], skip it.
  3. For each edge u → v with weight w: if d + w < dist[v], set dist[v] = d + w and push {dist[v], v}.
  4. When the heap is empty, return the maximum distance, or -1 if a node is unreachable.
static int dijkstra(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) -> Integer.compare(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, u was settled with a smaller time
        for (int[] e : adj.get(u)) {
            int v = e[0], w = e[1];
            if (d + w < dist[v]) {
                dist[v] = d + w;
                pq.offer(new int[]{dist[v], v});
            }
        }
    }
    return slowest(dist, n);
}

Dry run on Example 1 (k = 2):

pop stale? relaxations dist[1..4]
{0, 2} no dist[1] = 1, dist[3] = 1 [1, 0, 1, ∞]
{1, 1} no none (no outgoing edges) [1, 0, 1, ∞]
{1, 3} no dist[4] = 2 [1, 0, 1, 2]
{2, 4} no none [1, 0, 1, 2]

The largest value is 2, so the answer is 2.

Complexity. Time O(E log E): each edge can push at most one heap entry, and each push or pop costs O(log E). Since E ≤ n², this is the same as O(E log n). Space O(n + E) for the adjacency list and the heap.

For very dense graphs, a heap-free Dijkstra that scans an array for the minimum unsettled node runs in O(n²), which can beat O(E log E) when E is close to n². For this problem’s sizes both are instant.

Why the answer is the maximum, not the sum

It is tempting to add up edge weights along some spanning structure, but the signal travels along all edges in parallel. Node v hears the signal at time dist[v] regardless of what happens elsewhere. The network is fully informed at the moment the last node hears it, which is max(dist[v]). A sum would only be right if a single messenger had to walk to every node in turn, which is a different (and much harder) problem.

Edge cases and pitfalls