SyntaxPilot
Courses/DSA and Coding Problems/Lesson 52
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

DSA and Coding Problems · Lesson 52 of 90

Dijkstra's algorithm: network delay time

queued

These are the notes for DSA episode 52. BFS (episode 47) finds the path with the fewest edges. But when every edge has its own length, its weight, the shortest path is the one with the smallest sum of weights, and BFS gives wrong answers. We start from a real-life problem (a flood alert hopping between relay towers), define every word, try two obvious ideas (BFS gives 10 instead of 2 on a detour, and trying every path is correct but hits Time Limit Exceeded on a ladder of only 61 towers: 2^30 paths), find the key insight (with no negative weights, the waiting tower with the smallest known time is final), and finish with Dijkstra's algorithm with a priority queue, in O((V + E) log V). Every program below was run with javac 21 with an 8-second limit (like the SyntaxPilot compiler), and every output shown is real.

The problem, in real life

A flood alert leaves the district control room and hops from relay tower to relay tower. Each link sends one way, and each link has its own delay: 10 milliseconds on one, 1 millisecond on another. How long until every tower has the alert? And is there a tower that never gets it?

With the alert In code
A relay tower a vertex 1..n
A one-way link with a delay a weighted directed edge {u, v, w}
The delay of a link the edge's weight w
The time the alert takes along a route the path length = the sum of the weights
The earliest time tower v can get it dist[v], the shortest distance
When every tower has it max(dist[v]) over all towers
A tower no route reaches dist[v] = ∞ → answer -1

Every word, from zero

  • Weighted edge u → v with weight w: a one-way link with a number on it (here a delay in ms).
  • Path length: the sum of the weights along a path. Not the number of hops.
  • Shortest distance dist[v]: the smallest path length from the start k to v.
  • Infinity (∞): "not reached yet". In Java we use Integer.MAX_VALUE = 2147483647.
  • Relaxing an edge u → v, w: if dist[u] + w < dist[v], we found a faster way to v: update dist[v].
  • Settled: a vertex whose dist is known to be final.
  • Greedy: always take the choice that looks best right now; it works here because of the proof below.
  • Priority queue / min-heap (episode 43): poll() always returns the smallest element. Java: PriorityQueue with a comparator.
  • Stale entry: an old (v, time) pair still in the heap after dist[v] was improved. We skip it when polled.
  • Lazy deletion: instead of changing an entry inside the heap (Java's PriorityQueue can't), push a new pair and skip stale ones.
  • Negative weight: a weight below 0 (like a cashback). Dijkstra requires all weights ≥ 0.

Problem statement

LeetCode 743, Network Delay Time. You are given a network of n nodes labelled 1 to n, and times[i] = (u, v, w): a signal from u reaches v after w time. We send a signal from node k. Return the minimum time it takes for all n nodes to receive it; if that is impossible, return -1.

times n k Answer
[[2,1,1],[2,3,1],[3,4,1]] 4 2 2
[[1,2,1]] 2 1 1
[[1,2,1]] 2 2 -1 (nothing leaves node 2)

Constraints: 1 ≤ n ≤ 100, 1 ≤ times.length ≤ 6000, 0 ≤ w ≤ 100. We also test a 1 lakh-tower network.

All programs use this helper: an adjacency list where each entry is {neighbour, weight}, with n + 1 lists because towers start at 1.

    static List<List<int[]>> build(int[][] times, int n) {
        List<List<int[]>> adj = new ArrayList<>();
        for (int v = 0; v <= n; v++) adj.add(new ArrayList<>());
        for (int[] t : times) adj.get(t[0]).add(new int[]{t[1], t[2]});
        return adj;
    }

Obvious idea 1: BFS from episode 47

Give each tower a time the first time BFS reaches it: its parent's time plus the link.

import java.util.*;

public class Main {
    static List<List<int[]>> build(int[][] times, int n) {
        List<List<int[]>> adj = new ArrayList<>();
        for (int v = 0; v <= n; v++) adj.add(new ArrayList<>());
        for (int[] t : times) adj.get(t[0]).add(new int[]{t[1], t[2]});
        return adj;
    }
    static int networkDelayTime(int[][] times, int n, int k) {
        List<List<int[]>> adj = build(times, n);
        int[] dist = new int[n + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[k] = 0;
        Deque<Integer> q = new ArrayDeque<>();
        q.add(k);
        while (!q.isEmpty()) {
            int u = q.poll();
            for (int[] e : adj.get(u))
                if (dist[e[0]] == Integer.MAX_VALUE) { dist[e[0]] = dist[u] + e[1]; q.add(e[0]); }
        }
        int ans = 0;
        for (int v = 1; v <= n; v++) {
            if (dist[v] == Integer.MAX_VALUE) return -1;
            ans = Math.max(ans, dist[v]);
        }
        return ans;
    }
    public static void main(String[] args) {
        System.out.println(networkDelayTime(new int[][]{{2, 1, 1}, {2, 3, 1}, {3, 4, 1}}, 4, 2));
        System.out.println(networkDelayTime(new int[][]{{1, 2, 1}}, 2, 1));
        System.out.println(networkDelayTime(new int[][]{{1, 2, 1}}, 2, 2));
        System.out.println(networkDelayTime(new int[][]{{1, 2, 10}, {1, 3, 1}, {3, 2, 1}}, 3, 1));
    }
}
2
1
-1
10

The three LeetCode examples are right, but the fourth test, a slow direct link 1 → 2 (10 ms) and a fast detour 1 → 3 → 2 (1 + 1 ms), gives 10 instead of 2.

Why: BFS reaches tower 2 first through the direct link, because it is one hop, and never changes it. BFS is right when every edge counts the same; with weights, fewer hops is not less time.

Obvious idea 2: try every path, keep improving

dfs(u, t) means "we reached u at time t". If t is not better than dist[u], stop; otherwise record it and continue along every link.

import java.util.*;

public class Main {
    static List<List<int[]>> build(int[][] times, int n) {
        List<List<int[]>> adj = new ArrayList<>();
        for (int v = 0; v <= n; v++) adj.add(new ArrayList<>());
        for (int[] t : times) adj.get(t[0]).add(new int[]{t[1], t[2]});
        return adj;
    }
    static int networkDelayTime(int[][] times, int n, int k) {
        List<List<int[]>> adj = build(times, n);
        int[] dist = new int[n + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dfs(adj, k, 0, dist);
        int ans = 0;
        for (int v = 1; v <= n; v++) {
            if (dist[v] == Integer.MAX_VALUE) return -1;
            ans = Math.max(ans, dist[v]);
        }
        return ans;
    }
    static void dfs(List<List<int[]>> adj, int u, int t, int[] dist) {
        if (t >= dist[u]) return;
        dist[u] = t;
        for (int[] e : adj.get(u)) dfs(adj, e[0], t + e[1], dist);
    }
    public static void main(String[] args) {
        System.out.println(networkDelayTime(new int[][]{{2, 1, 1}, {2, 3, 1}, {3, 4, 1}}, 4, 2));
        System.out.println(networkDelayTime(new int[][]{{1, 2, 1}}, 2, 1));
        System.out.println(networkDelayTime(new int[][]{{1, 2, 1}}, 2, 2));
        System.out.println(networkDelayTime(new int[][]{{1, 2, 10}, {1, 3, 1}, {3, 2, 1}}, 3, 1));
    }
}
2
1
-1
2

Correct, including the detour. Now a ladder of 30 diamonds: each diamond has a slow direct link (listed first) and a faster two-link detour, with the slow links' extra cost halving from one diamond to the next. Only 61 towers:

        int d = 30, n = 2 * d + 1;
        int[][] times = new int[3 * d][];
        for (int i = 0; i < d; i++) {
            int a = 2 * i + 1;
            times[3 * i] = new int[]{a, a + 2, 2 + (1 << (d - 1 - i))};
            times[3 * i + 1] = new int[]{a, a + 1, 1};
            times[3 * i + 2] = new int[]{a + 1, a + 2, 1};
        }
        long t0 = System.nanoTime();
        int ans = networkDelayTime(times, n, 1);
        System.out.println(ans + " delay, " + (System.nanoTime() - t0) / 1000000 + " ms");
(no output: Time Limit Exceeded after 8 seconds)

Why it explodes: each diamond has 2 ways through and the DFS tries the slow one first. Every time it finds a better time for a tower, it re-explores everything after it. The extra costs are chosen so that every combination of choices gives a different, better time, so all 2 × 2 × ... × 2 = 2^30 ≈ 107 crore paths are explored. The waste: we keep updating times that later get beaten.

Could we know, for sure, that a tower's time is already final?

The key insight: the earliest waiting tower is final

Among all the towers still waiting, look at the one with the smallest known time, say tower u with time d. Could any other route reach u sooner? Any other route must leave the settled towers through some other waiting tower x, which already has a time ≥ d, and the rest of the route can only add time, because no weight is negative. So d is final: u is settled.

Then u passes the alert on: for each link u → v, w, if d + w < dist[v], update dist[v] (relax the edge). Repeat: settle the next smallest. That is Dijkstra's algorithm, published by Edsger W. Dijkstra in 1959.

Walkthrough (start 1; links 1→2 (4), 1→3 (1), 3→2 (2), 2→4 (1), 3→4 (5), 4→5 (3)):

settle 1 at 0:  relax → 2 = 4, 3 = 1
settle 3 at 1:  relax → 2 = 1+2 = 3 (better than 4), 4 = 1+5 = 6
settle 2 at 3:  relax → 4 = 3+1 = 4 (better than 6)
settle 4 at 4:  relax → 5 = 4+3 = 7
settle 5 at 7.  The last tower gets it at 7.

With a priority queue:

  1. dist[] = ∞, dist[k] = 0, push (k, 0).
  2. Poll the smallest (u, d).
  3. If d > dist[u], it's a stale entry: skip it.
  4. For each link u → v, w: if d + w < dist[v], set dist[v] = d + w and push (v, d + w).
  5. Answer: max(dist[1..n]), or -1 if any is still ∞.

The optimal solution in Java: Dijkstra with a PriorityQueue

import java.util.*;

public class Main {
    static List<List<int[]>> build(int[][] times, int n) {
        List<List<int[]>> adj = new ArrayList<>();
        for (int v = 0; v <= n; v++) adj.add(new ArrayList<>());
        for (int[] t : times) adj.get(t[0]).add(new int[]{t[1], t[2]});
        return adj;
    }
    static int networkDelayTime(int[][] times, int n, int k) {
        List<List<int[]>> adj = build(times, n);
        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[1], b[1]));
        pq.add(new int[]{k, 0});
        while (!pq.isEmpty()) {
            int[] top = pq.poll();
            int u = top[0], d = top[1];
            if (d > dist[u]) continue;
            for (int[] e : adj.get(u))
                if (d + e[1] < dist[e[0]]) {
                    dist[e[0]] = d + e[1];
                    pq.add(new int[]{e[0], dist[e[0]]});
                }
        }
        int ans = 0;
        for (int v = 1; v <= n; v++) {
            if (dist[v] == Integer.MAX_VALUE) return -1;
            ans = Math.max(ans, dist[v]);
        }
        return ans;
    }
    public static void main(String[] args) {
        System.out.println(networkDelayTime(new int[][]{{2, 1, 1}, {2, 3, 1}, {3, 4, 1}}, 4, 2));
        System.out.println(networkDelayTime(new int[][]{{1, 2, 1}}, 2, 1));
        System.out.println(networkDelayTime(new int[][]{{1, 2, 1}}, 2, 2));
        System.out.println(networkDelayTime(new int[][]{{1, 2, 10}, {1, 3, 1}, {3, 2, 1}}, 3, 1));
        System.out.println(networkDelayTime(new int[][]{}, 1, 1));
        System.out.println(networkDelayTime(new int[][]{{1, 2, 5}, {2, 3, 0}}, 3, 1));
    }
}
2
1
-1
2
0
5

The three examples, the detour (2, not 10), a single tower with no links (0), and a zero-delay link (5): weight 0 is allowed.

Line by line:

  • PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[1], b[1])): pairs {tower, time}, smallest time first. Integer.compare avoids the overflow that a[1] - b[1] can have with huge numbers.
  • if (d > dist[u]) continue;: lazy deletion. A better time for u was found after this pair was pushed.
  • The relax step updates dist and pushes the new pair.

The ladder that had 2^30 paths:

60 delay, 27 ms

A 1 lakh-tower network (a chain plus a lakh random links with random delays):

        int n = 100000;
        int[][] times = new int[2 * n][];
        Random rnd = new Random(7);
        for (int i = 0; i < 2 * n; i++) {
            int u = i < n - 1 ? i + 1 : 1 + rnd.nextInt(n), v = i < n - 1 ? i + 2 : 1 + rnd.nextInt(n);
            times[i] = new int[]{u, v, 1 + rnd.nextInt(100)};
        }
        long t0 = System.nanoTime();
        int ans = networkDelayTime(times, n, 1);
        System.out.println(ans + " delay, " + (System.nanoTime() - t0) / 1000000 + " ms");
1317 delay, 253 ms

The same solution in C++

#include <bits/stdc++.h>
using namespace std;

int networkDelayTime(const vector<vector<int>>& times, int n, int k) {
    vector<vector<pair<int, int>>> adj(n + 1);              // towers 1..n: size n + 1
    for (auto& t : times) adj[t[0]].push_back({t[1], t[2]});
    vector<int> dist(n + 1, INT_MAX);
    dist[k] = 0;
    // min-heap of {time, tower}: greater<> puts the smallest time on top
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
    pq.push({0, k});
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist[u]) continue;                          // stale entry
        for (auto [v, w] : adj[u])
            if (d + w < dist[v]) { dist[v] = d + w; pq.push({dist[v], v}); }
    }
    int ans = 0;
    for (int v = 1; v <= n; v++) {
        if (dist[v] == INT_MAX) return -1;
        ans = max(ans, dist[v]);
    }
    return ans;
}

int main() {
    cout << networkDelayTime({{2, 1, 1}, {2, 3, 1}, {3, 4, 1}}, 4, 2) << "\n";   // 2
    cout << networkDelayTime({{1, 2, 1}}, 2, 1) << "\n";                         // 1
    cout << networkDelayTime({{1, 2, 1}}, 2, 2) << "\n";                         // -1
    cout << networkDelayTime({{1, 2, 10}, {1, 3, 1}, {3, 2, 1}}, 3, 1) << "\n";  // 2 (the detour)
}
2
1
-1
2

C++'s priority_queue is a max-heap by default; greater<> turns it into a min-heap. The pair is {time, tower} so that it is ordered by time.

The same solution in Python

import heapq

def network_delay_time(times, n, k):
    adj = [[] for _ in range(n + 1)]          # towers 1..n
    for u, v, w in times:
        adj[u].append((v, w))
    INF = float("inf")
    dist = [INF] * (n + 1)
    dist[k] = 0
    pq = [(0, k)]                             # heapq is a min-heap of (time, tower)
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:                       # stale entry
            continue
        for v, w in adj[u]:
            if d + w < dist[v]:
                dist[v] = d + w
                heapq.heappush(pq, (dist[v], v))
    ans = max(dist[1:])
    return -1 if ans == INF else ans

print(network_delay_time([[2, 1, 1], [2, 3, 1], [3, 4, 1]], 4, 2))    # 2
print(network_delay_time([[1, 2, 1]], 2, 1))                          # 1
print(network_delay_time([[1, 2, 1]], 2, 2))                          # -1
print(network_delay_time([[1, 2, 10], [1, 3, 1], [3, 2, 1]], 3, 1))   # 2
2
1
-1
2

heapq is a min-heap on a plain list; tuples compare by their first item, the time.

Three real bugs

Bug 1: marking a tower "done" when it is pushed (a BFS habit)

import java.util.*;

public class Main {
    static List<List<int[]>> build(int[][] times, int n) {
        List<List<int[]>> adj = new ArrayList<>();
        for (int v = 0; v <= n; v++) adj.add(new ArrayList<>());
        for (int[] t : times) adj.get(t[0]).add(new int[]{t[1], t[2]});
        return adj;
    }
    static int networkDelayTime(int[][] times, int n, int k) {
        List<List<int[]>> adj = build(times, n);
        int[] dist = new int[n + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[k] = 0;
        boolean[] done = new boolean[n + 1];
        done[k] = true;
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[1], b[1]));
        pq.add(new int[]{k, 0});
        while (!pq.isEmpty()) {
            int[] top = pq.poll();
            int u = top[0], d = top[1];
            if (d > dist[u]) continue;
            for (int[] e : adj.get(u))
                if (!done[e[0]]) {
                    done[e[0]] = true;
                    dist[e[0]] = d + e[1];
                    pq.add(new int[]{e[0], dist[e[0]]});
                }
        }
        int ans = 0;
        for (int v = 1; v <= n; v++) {
            if (dist[v] == Integer.MAX_VALUE) return -1;
            ans = Math.max(ans, dist[v]);
        }
        return ans;
    }
    public static void main(String[] args) {
        System.out.println(networkDelayTime(new int[][]{{1, 2, 10}, {1, 3, 1}, {3, 2, 1}}, 3, 1));
    }
}
10

10 instead of 2. Being pushed does not make a time final. A tower is final only when it is polled as the smallest.

Bug 2: an array of size n for towers 1..n

import java.util.*;

public class Main {
    static List<List<int[]>> build(int[][] times, int n) {
        List<List<int[]>> adj = new ArrayList<>();
        for (int v = 0; v <= n; v++) adj.add(new ArrayList<>());
        for (int[] t : times) adj.get(t[0]).add(new int[]{t[1], t[2]});
        return adj;
    }
    static int networkDelayTime(int[][] times, int n, int k) {
        List<List<int[]>> adj = build(times, n);
        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[k] = 0;
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[1], b[1]));
        pq.add(new int[]{k, 0});
        while (!pq.isEmpty()) {
            int[] top = pq.poll();
            int u = top[0], d = top[1];
            if (d > dist[u]) continue;
            for (int[] e : adj.get(u))
                if (d + e[1] < dist[e[0]]) {
                    dist[e[0]] = d + e[1];
                    pq.add(new int[]{e[0], dist[e[0]]});
                }
        }
        int ans = 0;
        for (int v = 1; v <= n; v++) {
            if (dist[v] == Integer.MAX_VALUE) return -1;
            ans = Math.max(ans, dist[v]);
        }
        return ans;
    }
    public static void main(String[] args) {
        System.out.println(networkDelayTime(new int[][]{{2, 1, 1}, {2, 3, 1}, {3, 4, 1}}, 4, 2));
        System.out.println(networkDelayTime(new int[][]{{1, 2, 1}}, 2, 1));
        System.out.println(networkDelayTime(new int[][]{{1, 2, 1}}, 2, 2));
    }
}
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 4 out of bounds for length 4
    at Main.networkDelayTime(Main.java:22)
    at Main.main(Main.java:35)

Tower 4 needs index 4, so dist must have n + 1 places.

Bug 3: no unreachable check

import java.util.*;

public class Main {
    static List<List<int[]>> build(int[][] times, int n) {
        List<List<int[]>> adj = new ArrayList<>();
        for (int v = 0; v <= n; v++) adj.add(new ArrayList<>());
        for (int[] t : times) adj.get(t[0]).add(new int[]{t[1], t[2]});
        return adj;
    }
    static int networkDelayTime(int[][] times, int n, int k) {
        List<List<int[]>> adj = build(times, n);
        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[1], b[1]));
        pq.add(new int[]{k, 0});
        while (!pq.isEmpty()) {
            int[] top = pq.poll();
            int u = top[0], d = top[1];
            if (d > dist[u]) continue;
            for (int[] e : adj.get(u))
                if (d + e[1] < dist[e[0]]) {
                    dist[e[0]] = d + e[1];
                    pq.add(new int[]{e[0], dist[e[0]]});
                }
        }
        int ans = 0;
        for (int v = 1; v <= n; v++) {
            ans = Math.max(ans, dist[v]);
        }
        return ans;
    }
    public static void main(String[] args) {
        System.out.println(networkDelayTime(new int[][]{{2, 1, 1}, {2, 3, 1}, {3, 4, 1}}, 4, 2));
        System.out.println(networkDelayTime(new int[][]{{1, 2, 1}}, 2, 1));
        System.out.println(networkDelayTime(new int[][]{{1, 2, 1}}, 2, 2));
    }
}
2
1
2147483647

2147483647 instead of -1 for the third example: Integer.MAX_VALUE, our infinity, printed as an answer.

Why negative weights break Dijkstra

Settling the smallest time is safe only because other routes can only add time. With a negative weight, a route that looks more expensive now can get cheaper later: 1 → 2 (2), 1 → 3 (5), 3 → 2 (-4). Tower 2 is settled at 2, but 1 → 3 → 2 costs 5 - 4 = 1. The classic algorithm (settle each vertex once, never touch it again) gets it wrong:

import java.util.*;

public class Main {
    // A negative weight breaks the classic Dijkstra (each tower settled ONCE, never touched again).
    public static void main(String[] args) {
        int n = 3, s = 1;
        int[][] times = {{1, 2, 2}, {1, 3, 5}, {3, 2, -4}};
        List<List<int[]>> adj = new ArrayList<>();
        for (int v = 0; v <= n; v++) 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[s] = 0;
        boolean[] settled = new boolean[n + 1];
        for (int round = 0; round < n; round++) {
            int u = -1;                                   // the unsettled tower with the smallest time
            for (int v = 1; v <= n; v++) if (!settled[v] && dist[v] != Integer.MAX_VALUE && (u == -1 || dist[v] < dist[u])) u = v;
            if (u == -1) break;
            settled[u] = true;
            for (int[] e : adj.get(u))
                if (!settled[e[0]] && dist[u] + e[1] < dist[e[0]]) dist[e[0]] = dist[u] + e[1];
        }
        System.out.println("classic Dijkstra: dist[2] = " + dist[2] + "   (true shortest: 1 -> 3 -> 2 = 5 - 4 = 1)");
    }
}
classic Dijkstra: dist[2] = 2   (true shortest: 1 -> 3 -> 2 = 5 - 4 = 1)

(The lazy-deletion version above happens to re-push tower 2 here, but with negative weights it loses its guarantee and can take exponential time.) For negative weights use Bellman-Ford (next episode).

Complexity

Approach Time Space Test
BFS (fewest hops) O(V + E) O(V + E) wrong answer (10 instead of 2)
Try every path (DFS) exponential O(V + E) 61-tower ladder: Time Limit Exceeded
Dijkstra + min-heap O((V + E) log V) O(V + E) 1 lakh towers, 2 lakh links: a fraction of a second
Dijkstra with an array scan (no heap) O(V²) O(V + E) fine for small dense graphs

Each tower is settled once and each link relaxed once; every heap push/poll costs O(log(heap size)), and the heap holds at most E + 1 entries, so O((V + E) log V).

Common mistakes

Mistake What you see (real) Why Fix
BFS on weighted edges 10 instead of 2 fewer hops ≠ less time a min-heap by time
done[] when pushing 10 instead of 2 pushed is not final final when polled
new int[n] for towers 1..n ArrayIndexOutOfBoundsException: Index 4 out of bounds for length 4 index n needed size n + 1
No ∞ check 2147483647 unreached = MAX_VALUE return -1
Comparator a[1] - b[1] with huge values wrong order (overflow) subtraction overflows Integer.compare(a[1], b[1])
Negative weights wrong distances the greedy proof breaks Bellman-Ford

Mini project: the flood-alert report

For every tower: when it gets the alert, the last tower overall, and towers that never get it.

import java.util.*;

public class Main {
    // Mini project: the flood-alert report. For every tower: when it gets the alert, and the last tower overall.
    public static void main(String[] args) {
        String[] name = {"", "Control room", "Hill tower", "River tower", "Market tower", "School tower", "Island tower"};
        int n = 6, k = 1;
        int[][] links = {{1, 2, 4}, {1, 3, 1}, {3, 2, 2}, {2, 4, 1}, {3, 4, 5}, {4, 5, 3}};   // tower 6 has no link
        List<List<int[]>> adj = new ArrayList<>();
        for (int v = 0; v <= n; v++) adj.add(new ArrayList<>());
        for (int[] t : links) 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[1], b[1]));
        pq.add(new int[]{k, 0});
        while (!pq.isEmpty()) {
            int[] top = pq.poll(); int u = top[0], d = top[1];
            if (d > dist[u]) continue;
            for (int[] e : adj.get(u))
                if (d + e[1] < dist[e[0]]) { dist[e[0]] = d + e[1]; pq.add(new int[]{e[0], dist[e[0]]}); }
        }
        int last = 0; List<String> never = new ArrayList<>();
        for (int v = 1; v <= n; v++) {
            if (dist[v] == Integer.MAX_VALUE) { never.add(name[v]); System.out.printf("%-13s never%n", name[v]); continue; }
            System.out.printf("%-13s %3d ms%n", name[v], dist[v]);
            last = Math.max(last, dist[v]);
        }
        System.out.println(never.isEmpty() ? "Every tower has the alert after " + last + " ms" : "Unreachable: " + never + " (answer -1)");
    }
}
Control room    0 ms
Hill tower      3 ms
River tower     1 ms
Market tower    4 ms
School tower    7 ms
Island tower  never
Unreachable: [Island tower] (answer -1)

Practice

1. Print the shortest path itself.

Solution

Whenever dist[v] improves, remember parent[v] = u. Walk the parents back from any tower and reverse.

import java.util.*;

public class Main {
    // Print the shortest path itself: remember the parent (the tower we came from) whenever dist improves.
    public static void main(String[] args) {
        int n = 5, k = 1;
        int[][] times = {{1, 2, 4}, {1, 3, 1}, {3, 2, 2}, {2, 4, 1}, {3, 4, 5}, {4, 5, 3}};
        List<List<int[]>> adj = new ArrayList<>();
        for (int v = 0; v <= n; v++) 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], parent = new int[n + 1];
        Arrays.fill(dist, Integer.MAX_VALUE); Arrays.fill(parent, -1);
        dist[k] = 0;
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[1], b[1]));
        pq.add(new int[]{k, 0});
        while (!pq.isEmpty()) {
            int[] top = pq.poll(); int u = top[0], d = top[1];
            if (d > dist[u]) continue;
            for (int[] e : adj.get(u))
                if (d + e[1] < dist[e[0]]) { dist[e[0]] = d + e[1]; parent[e[0]] = u; pq.add(new int[]{e[0], dist[e[0]]}); }
        }
        for (int v = 1; v <= n; v++) {
            List<Integer> path = new ArrayList<>();
            for (int x = v; x != -1; x = parent[x]) path.add(x);
            Collections.reverse(path);
            System.out.println("tower " + v + ": time " + dist[v] + ", path " + path);
        }
    }
}
tower 1: time 0, path [1]
tower 2: time 3, path [1, 3, 2]
tower 3: time 1, path [1, 3]
tower 4: time 4, path [1, 3, 2, 4]
tower 5: time 7, path [1, 3, 2, 4, 5]

2. Path With Minimum Effort (LeetCode 1631). Walk from the top-left to the bottom-right of a height grid; a path's effort is its biggest height difference between neighbouring cells. Minimise the effort.

Solution

Dijkstra on the grid, where a path's "length" is the max step instead of the sum. It still never decreases along a path, so the smallest popped value is final.

import java.util.*;

public class Main {
    // Path With Minimum Effort (LeetCode 1631): effort of a path = the biggest height step on it. Minimise it.
    // Dijkstra still works: "length" = max instead of sum, and it never decreases along a path.
    static int minimumEffortPath(int[][] h) {
        int R = h.length, C = h[0].length;
        int[][] best = new int[R][C];
        for (int[] row : best) Arrays.fill(row, Integer.MAX_VALUE);
        best[0][0] = 0;
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[2], b[2]));
        pq.add(new int[]{0, 0, 0});
        int[][] d = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        while (!pq.isEmpty()) {
            int[] t = pq.poll(); int r = t[0], c = t[1], e = t[2];
            if (e > best[r][c]) continue;
            if (r == R - 1 && c == C - 1) return e;
            for (int[] k : d) {
                int y = r + k[0], x = c + k[1];
                if (y < 0 || x < 0 || y >= R || x >= C) continue;
                int ne = Math.max(e, Math.abs(h[y][x] - h[r][c]));
                if (ne < best[y][x]) { best[y][x] = ne; pq.add(new int[]{y, x, ne}); }
            }
        }
        return 0;
    }
    public static void main(String[] args) {
        System.out.println(minimumEffortPath(new int[][]{{1, 2, 2}, {3, 8, 2}, {5, 3, 5}}));
        System.out.println(minimumEffortPath(new int[][]{{1, 2, 3}, {3, 8, 4}, {5, 3, 5}}));
    }
}
2
1

3. Path with Maximum Probability (LeetCode 1514). Each undirected edge has a success probability; find the most likely path from start to end.

Solution

Multiply instead of add, and use a max-heap: multiplying by a probability ≤ 1 never increases it, so the largest popped value is final.

import java.util.*;

public class Main {
    // Path with Maximum Probability (LeetCode 1514): multiply probabilities, maximise. A max-heap Dijkstra:
    // multiplying by a number <= 1 never increases the probability, so the largest one popped is final.
    static double maxProbability(int n, int[][] edges, double[] p, int s, int t) {
        List<List<double[]>> adj = new ArrayList<>();
        for (int v = 0; v < n; v++) adj.add(new ArrayList<>());
        for (int i = 0; i < edges.length; i++) {
            adj.get(edges[i][0]).add(new double[]{edges[i][1], p[i]});
            adj.get(edges[i][1]).add(new double[]{edges[i][0], p[i]});
        }
        double[] best = new double[n];
        best[s] = 1;
        PriorityQueue<double[]> pq = new PriorityQueue<>((a, b) -> Double.compare(b[1], a[1]));
        pq.add(new double[]{s, 1});
        while (!pq.isEmpty()) {
            double[] top = pq.poll(); int u = (int) top[0]; double pr = top[1];
            if (pr < best[u]) continue;
            if (u == t) return pr;
            for (double[] e : adj.get(u)) {
                int v = (int) e[0]; double np = pr * e[1];
                if (np > best[v]) { best[v] = np; pq.add(new double[]{v, np}); }
            }
        }
        return 0;
    }
    public static void main(String[] args) {
        System.out.println(maxProbability(3, new int[][]{{0, 1}, {1, 2}, {0, 2}}, new double[]{0.5, 0.5, 0.2}, 0, 2));
        System.out.println(maxProbability(3, new int[][]{{0, 1}}, new double[]{0.5}, 0, 2));
    }
}
0.25
0.0

4. Find a graph where a negative edge breaks Dijkstra.

Solution

See the section "Why negative weights break Dijkstra" above: 1 → 2 (2), 1 → 3 (5), 3 → 2 (-4). The classic algorithm settles tower 2 at 2; the true shortest is 1.

Quick quiz

Links: 1→2 (3), 1→3 (1), 3→2 (1), 2→4 (2); n = 4, k = 1. Network delay time? A) 4 B) 5 C) 3 D) 6

Answer

A) 4. dist[3] = 1, dist[2] = 2 (through 3, not the direct 3), dist[4] = 2 + 2 = 4. The last tower gets it at 4.

Interview questions

  1. Why does BFS fail with weights? It finalises a vertex the first time it is reached, by the fewest edges; a path with more edges can be shorter in total weight.
  2. Why is the smallest popped distance final? Every other route to it passes through a vertex with a distance at least as big, and non-negative weights can only add to it.
  3. What is lazy deletion and why is it needed in Java? PriorityQueue has no decrease-key; push a new pair and skip polled pairs with d > dist[u].
  4. Complexity? O((V + E) log V) with a binary heap; O(V²) with an array scan (better for very dense graphs).
  5. Can weights be 0? Negative? 0 is fine. Negative is not: use Bellman-Ford (or Johnson's algorithm for all pairs).
  6. How do you get the path, not just the distance? Store parent[v] when relaxing; walk back from the target.
  7. How would you stop early for one target? Return as soon as the target is polled (practice 2 does this).

Glossary

Term Meaning
Weight The number on an edge (here a delay)
Weighted directed edge A one-way link u → v with weight w
Path length The sum of the weights on a path
dist[v] The shortest known distance from the start to v
Infinity "Not reached yet"; Integer.MAX_VALUE
Relax Improve dist[v] through u if dist[u] + w is smaller
Settled A vertex whose distance is final
Greedy Always take the best-looking choice now
Priority queue / min-heap poll() gives the smallest element
Stale entry An outdated pair still in the heap
Lazy deletion Push again; skip stale pairs when polled
Negative weight A weight below 0; breaks Dijkstra
Bellman-Ford Shortest paths that allow negative weights (next episode)
O((V + E) log V) Dijkstra's time with a binary heap

Summary

  • With weights, a path's length is the sum of its weights: BFS gives wrong answers, and trying every path is exponential.
  • Dijkstra: with no negative weights, the waiting vertex with the smallest time is final; settle it, relax its edges, repeat.
  • Java: PriorityQueue of {vertex, time}, Integer.compare, and lazy deletion (if (d > dist[u]) continue;).
  • Final when polled, not when pushed; arrays of size n + 1 for 1-based vertices; ∞ → -1.
  • O((V + E) log V) time, O(V + E) space.
  • Next episode: Bellman-Ford and cheapest flights within K stops.