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 → vwith weightw: 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 startktov. - Infinity (∞): "not reached yet". In Java we use
Integer.MAX_VALUE=2147483647. - Relaxing an edge
u → v, w: ifdist[u] + w < dist[v], we found a faster way tov: updatedist[v]. - Settled: a vertex whose
distis 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:PriorityQueuewith a comparator. - Stale entry: an old
(v, time)pair still in the heap afterdist[v]was improved. We skip it when polled. - Lazy deletion: instead of changing an entry inside the heap (Java's
PriorityQueuecan'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:
dist[] = ∞,dist[k] = 0, push(k, 0).- Poll the smallest
(u, d). - If
d > dist[u], it's a stale entry: skip it. - For each link
u → v, w: ifd + w < dist[v], setdist[v] = d + wand push(v, d + w). - Answer:
max(dist[1..n]), or-1if 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.compareavoids the overflow thata[1] - b[1]can have with huge numbers.if (d > dist[u]) continue;: lazy deletion. A better time foruwas found after this pair was pushed.- The relax step updates
distand 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
- 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.
- 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.
- What is lazy deletion and why is it needed in Java?
PriorityQueuehas no decrease-key; push a new pair and skip polled pairs withd > dist[u]. - Complexity? O((V + E) log V) with a binary heap; O(V²) with an array scan (better for very dense graphs).
- Can weights be 0? Negative? 0 is fine. Negative is not: use Bellman-Ford (or Johnson's algorithm for all pairs).
- How do you get the path, not just the distance? Store
parent[v]when relaxing; walk back from the target. - 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:
PriorityQueueof{vertex, time},Integer.compare, and lazy deletion (if (d > dist[u]) continue;). - Final when polled, not when pushed; arrays of size
n + 1for 1-based vertices; ∞ → -1. - O((V + E) log V) time, O(V + E) space.
- Next episode: Bellman-Ford and cheapest flights within K stops.