These are the notes for DSA episode 53. Dijkstra (episode 52) keeps one best price per city, and that breaks in two situations: when the route may use at most K stops, and when an edge has a negative weight. We start from a real-life problem (Asha wants the cheapest Delhi to Goa ticket with at most one layover), define every word, try two obvious ideas (Dijkstra by price gives 400 instead of 700, and trying every route is correct but hits Time Limit Exceeded on only 40 cities: 2^38 routes), find the key insight (think in rounds of flights; each round is built only from a copy of the last round), and finish with Bellman-Ford in O(K × E), plus the full Bellman-Ford that handles negative weights and detects negative cycles. 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
Asha wants to fly from Delhi to Goa and wants the cheapest ticket. The cheapest routes often hop a lot (Delhi → Jaipur → Pune → Goa), and every city in between is a layover. But she has a meeting, so she accepts at most one layover. What is the cheapest price with at most K stops, and is there any such route at all?
| With the booking | In code |
|---|---|
| A city | a vertex 0..n-1 |
| A one-way flight with a fare | a weighted directed edge {from, to, price} |
| A layover | a stop: a city in between, not src and not dst |
| At most K layovers | at most K + 1 flights (edges) |
| The cheapest fare found so far | cost[v] |
| No route at all | answer -1 |
Every word, from zero
- Weighted directed edge: a one-way flight
u → vwith a number on it, its weight (here a price). - Stop: a city you pass through. A route with
fflights hasf - 1stops, so K stops = K + 1 flights. - Relaxing an edge
u → v, w: if reachingupluswis cheaper than what we know forv, updatev. - Round: one pass that relaxes every edge once. After round
i(from copies),cost[v]is the cheapest price using at mostiedges. - Bellman-Ford: shortest paths by repeating rounds of relaxing every edge (Richard Bellman and Lester Ford, 1950s).
- Negative weight: a weight below 0, like a cashback. Dijkstra cannot handle it; Bellman-Ford can.
- Negative cycle: a loop whose weights add up to less than 0. Going round it again and again lowers the price forever, so there is no shortest path.
- Infinity (∞): "not reachable yet". In Java
Integer.MAX_VALUE=2147483647; adding to it overflows. - Integer overflow: an
intthat goes past2147483647wraps around to a huge negative number.
Problem statement
LeetCode 787, Cheapest Flights Within K Stops. There are n cities 0..n-1 and flights[i] = [from, to, price]. Given src, dst and k, return the cheapest price from src to dst with at most k stops. If there is no such route, return -1.
| n | flights | src → dst | k | Answer |
|---|---|---|---|---|
| 4 | [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]] |
0 → 3 | 1 | 700 (0 → 1 → 3; the 400 route has 2 stops) |
| 3 | [[0,1,100],[1,2,100],[0,2,500]] |
0 → 2 | 1 | 200 |
| 3 | [[0,1,100],[1,2,100],[0,2,500]] |
0 → 2 | 0 | 500 (direct only) |
Constraints: 1 ≤ n ≤ 100, 0 ≤ flights.length ≤ n(n-1)/2, 1 ≤ price ≤ 10^4, no duplicate flights, 0 ≤ k < n.
Obvious idea 1: Dijkstra by price (episode 52)
Dijkstra finds the cheapest price to every city, ignoring how many flights it used.
import java.util.*;
public class Main {
static int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
List<List<int[]>> adj = new ArrayList<>();
for (int v = 0; v < n; v++) adj.add(new ArrayList<>());
for (int[] f : flights) adj.get(f[0]).add(new int[]{f[1], f[2]});
int[] dist = new int[n];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[src] = 0;
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[1], b[1]));
pq.add(new int[]{src, 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]]});
}
}
return dist[dst] == Integer.MAX_VALUE ? -1 : dist[dst];
}
public static void main(String[] args) {
int[][] ex1 = {{0, 1, 100}, {1, 2, 100}, {2, 0, 100}, {1, 3, 600}, {2, 3, 200}};
int[][] ex2 = {{0, 1, 100}, {1, 2, 100}, {0, 2, 500}};
System.out.println(findCheapestPrice(4, ex1, 0, 3, 1));
System.out.println(findCheapestPrice(3, ex2, 0, 2, 1));
System.out.println(findCheapestPrice(3, ex2, 0, 2, 0));
}
}
400
200
200
Two of three are wrong (should be 700, 200, 500). In example 1 the cheapest route overall is 0 → 1 → 2 → 3 = 400, but it stops at 1 and 2. Dijkstra keeps only one price per city, so it throws away the costlier route with fewer stops (0 → 1 → 3 = 700), which is exactly the one we need.
Obvious idea 2: try every route with at most K + 1 flights
A DFS: we are at city u, with some flights left, having paid cost. At dst, keep the cheapest; with no flights left, stop; otherwise take every flight out of u.
import java.util.*;
public class Main {
static int best;
static int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
List<List<int[]>> adj = new ArrayList<>();
for (int v = 0; v < n; v++) adj.add(new ArrayList<>());
for (int[] f : flights) adj.get(f[0]).add(new int[]{f[1], f[2]});
best = Integer.MAX_VALUE;
dfs(adj, src, dst, k + 1, 0);
return best == Integer.MAX_VALUE ? -1 : best;
}
static void dfs(List<List<int[]>> adj, int u, int dst, int flightsLeft, int cost) {
if (u == dst) { best = Math.min(best, cost); return; }
if (flightsLeft == 0) return;
for (int[] e : adj.get(u)) dfs(adj, e[0], dst, flightsLeft - 1, cost + e[1]);
}
public static void main(String[] args) {
int[][] ex1 = {{0, 1, 100}, {1, 2, 100}, {2, 0, 100}, {1, 3, 600}, {2, 3, 200}};
int[][] ex2 = {{0, 1, 100}, {1, 2, 100}, {0, 2, 500}};
System.out.println(findCheapestPrice(4, ex1, 0, 3, 1));
System.out.println(findCheapestPrice(3, ex2, 0, 2, 1));
System.out.println(findCheapestPrice(3, ex2, 0, 2, 0));
}
}
700
200
500
Correct. Now 40 cities with a flight from every city to every later one (longer jumps a bit cheaper), any number of stops:
import java.util.*;
public class Main {
static int best;
static int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
List<List<int[]>> adj = new ArrayList<>();
for (int v = 0; v < n; v++) adj.add(new ArrayList<>());
for (int[] f : flights) adj.get(f[0]).add(new int[]{f[1], f[2]});
best = Integer.MAX_VALUE;
dfs(adj, src, dst, k + 1, 0);
return best == Integer.MAX_VALUE ? -1 : best;
}
static void dfs(List<List<int[]>> adj, int u, int dst, int flightsLeft, int cost) {
if (u == dst) { best = Math.min(best, cost); return; }
if (flightsLeft == 0) return;
for (int[] e : adj.get(u)) dfs(adj, e[0], dst, flightsLeft - 1, cost + e[1]);
}
public static void main(String[] args) {
int n = 40;
List<int[]> list = new ArrayList<>();
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++) list.add(new int[]{i, j, 1000 - (j - i)});
int[][] flights = list.toArray(new int[0][]);
long t0 = System.nanoTime();
int ans = findCheapestPrice(n, flights, 0, n - 1, n - 2);
System.out.println(ans + " rupees, " + (System.nanoTime() - t0) / 1000000 + " ms");
}
}
Time Limit Exceeded (stopped after 8 seconds)
Why it explodes: each of the 38 middle cities is either in the route or not, so there are 2^38 ≈ 27,000 crore routes. And the waste: we reach the same city after the same number of flights again and again, through different routes, and redo everything after it. To continue from a city, only one thing matters: the cheapest way to get there in that many flights.
The key insight: rounds of flights
Plan the trip one flight at a time.
- Round 0:
cost[src] = 0, every other city ∞. - Round i + 1: start from a copy of round
i's prices and relax every flight using only roundi's prices. Nowcost[v]= cheapest price with at mosti + 1flights. - Stop after K + 1 rounds = at most K stops.
Why the copy? If a round reads a price that was set in the same round, one round can chain two flights, and the stop limit is silently broken (bug 1 below).
By hand on example 1 (k = 1):
| Round | City 0 | City 1 | City 2 | City 3 |
|---|---|---|---|---|
| 0 (no flight) | 0 | ∞ | ∞ | ∞ |
| 1 (≤ 1 flight) | 0 | 100 | ∞ | ∞ |
| 2 (≤ 2 flights) | 0 | 100 | 200 | 700 |
| 3 (would allow 2 stops) | 0 | 100 | 200 | 400 |
We stop after round 2: 700.
The optimal solution in Java: Bellman-Ford with K + 1 rounds
static int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
int INF = Integer.MAX_VALUE;
int[] cost = new int[n];
Arrays.fill(cost, INF);
cost[src] = 0;
for (int round = 1; round <= k + 1; round++) {
int[] next = cost.clone();
for (int[] f : flights) {
int u = f[0], v = f[1], price = f[2];
if (cost[u] == INF) continue;
if (cost[u] + price < next[v]) next[v] = cost[u] + price;
}
cost = next;
}
return cost[dst] == INF ? -1 : cost[dst];
}
No heap and no adjacency list: just a loop over the list of flights. Run on the examples, a destination nobody flies to, and src == dst:
import java.util.*;
public class Main {
static int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
int INF = Integer.MAX_VALUE;
int[] cost = new int[n];
Arrays.fill(cost, INF);
cost[src] = 0;
for (int round = 1; round <= k + 1; round++) {
int[] next = cost.clone();
for (int[] f : flights) {
int u = f[0], v = f[1], price = f[2];
if (cost[u] == INF) continue;
if (cost[u] + price < next[v]) next[v] = cost[u] + price;
}
cost = next;
}
return cost[dst] == INF ? -1 : cost[dst];
}
public static void main(String[] args) {
int[][] ex1 = {{0, 1, 100}, {1, 2, 100}, {2, 0, 100}, {1, 3, 600}, {2, 3, 200}};
int[][] ex2 = {{0, 1, 100}, {1, 2, 100}, {0, 2, 500}};
System.out.println(findCheapestPrice(4, ex1, 0, 3, 1));
System.out.println(findCheapestPrice(3, ex2, 0, 2, 1));
System.out.println(findCheapestPrice(3, ex2, 0, 2, 0));
System.out.println(findCheapestPrice(3, new int[][]{{0, 1, 100}}, 0, 2, 1));
System.out.println(findCheapestPrice(2, new int[][]{{0, 1, 300}}, 1, 1, 0));
}
}
700
200
500
-1
0
The 40 cities that timed out:
961 rupees, 0 ms
The biggest input LeetCode allows, 100 cities with a flight between every ordered pair (9,900 flights) and up to 98 stops:
import java.util.*;
public class Main {
static int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
int INF = Integer.MAX_VALUE;
int[] cost = new int[n];
Arrays.fill(cost, INF);
cost[src] = 0;
for (int round = 1; round <= k + 1; round++) {
int[] next = cost.clone();
for (int[] f : flights) {
int u = f[0], v = f[1], price = f[2];
if (cost[u] == INF) continue;
if (cost[u] + price < next[v]) next[v] = cost[u] + price;
}
cost = next;
}
return cost[dst] == INF ? -1 : cost[dst];
}
public static void main(String[] args) {
int n = 100;
List<int[]> list = new ArrayList<>();
Random rnd = new Random(7);
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (i != j) list.add(new int[]{i, j, 1 + rnd.nextInt(10000)});
int[][] flights = list.toArray(new int[0][]);
long t0 = System.nanoTime();
int ans = findCheapestPrice(n, flights, 0, n - 1, n - 2);
long ms = (System.nanoTime() - t0) / 1000000;
System.out.println(flights.length + " flights: " + ans + " rupees, " + ms + " ms");
}
}
9900 flights: 317 rupees, 17 ms
The same solution in C++
#include <bits/stdc++.h>
using namespace std;
// Cheapest Flights Within K Stops (LeetCode 787): Bellman-Ford with k + 1 rounds, each from a copy.
int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
const int INF = INT_MAX;
vector<int> cost(n, INF);
cost[src] = 0;
for (int round = 1; round <= k + 1; round++) {
vector<int> next = cost; // a copy: this round only uses last round's prices
for (auto& f : flights) {
int u = f[0], v = f[1], price = f[2];
if (cost[u] == INF) continue; // unreachable so far: skip (and no overflow)
if (cost[u] + price < next[v]) next[v] = cost[u] + price;
}
cost = next;
}
return cost[dst] == INF ? -1 : cost[dst];
}
int main() {
vector<vector<int>> ex1 = {{0, 1, 100}, {1, 2, 100}, {2, 0, 100}, {1, 3, 600}, {2, 3, 200}};
vector<vector<int>> ex2 = {{0, 1, 100}, {1, 2, 100}, {0, 2, 500}};
cout << findCheapestPrice(4, ex1, 0, 3, 1) << "\n";
cout << findCheapestPrice(3, ex2, 0, 2, 1) << "\n";
cout << findCheapestPrice(3, ex2, 0, 2, 0) << "\n";
}
700
200
500
The same solution in Python
# Cheapest Flights Within K Stops (LeetCode 787): Bellman-Ford with k + 1 rounds, each from a copy.
def find_cheapest_price(n, flights, src, dst, k):
INF = float("inf")
cost = [INF] * n
cost[src] = 0
for _ in range(k + 1):
nxt = cost[:] # a copy: this round only uses last round's prices
for u, v, price in flights:
if cost[u] + price < nxt[v]: # inf + price stays inf in Python: no overflow
nxt[v] = cost[u] + price
cost = nxt
return -1 if cost[dst] == INF else cost[dst]
ex1 = [[0, 1, 100], [1, 2, 100], [2, 0, 100], [1, 3, 600], [2, 3, 200]]
ex2 = [[0, 1, 100], [1, 2, 100], [0, 2, 500]]
print(find_cheapest_price(4, ex1, 0, 3, 1))
print(find_cheapest_price(3, ex2, 0, 2, 1))
print(find_cheapest_price(3, ex2, 0, 2, 0))
700
200
500
Three real bugs
Bug 1: no copy (next = cost)
import java.util.*;
public class Main {
static int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
int INF = Integer.MAX_VALUE;
int[] cost = new int[n];
Arrays.fill(cost, INF);
cost[src] = 0;
for (int round = 1; round <= k + 1; round++) {
int[] next = cost;
for (int[] f : flights) {
int u = f[0], v = f[1], price = f[2];
if (cost[u] == INF) continue;
if (cost[u] + price < next[v]) next[v] = cost[u] + price;
}
cost = next;
}
return cost[dst] == INF ? -1 : cost[dst];
}
public static void main(String[] args) {
int[][] ex1 = {{0, 1, 100}, {1, 2, 100}, {2, 0, 100}, {1, 3, 600}, {2, 3, 200}};
int[][] ex2 = {{0, 1, 100}, {1, 2, 100}, {0, 2, 500}};
System.out.println(findCheapestPrice(4, ex1, 0, 3, 1));
System.out.println(findCheapestPrice(3, ex2, 0, 2, 1));
System.out.println(findCheapestPrice(3, ex2, 0, 2, 0));
}
}
400
200
200
400 again, and 200 instead of 500 with zero stops. City 1 got its price in round 1, and in the same round we flew on from it: one round hid two flights. Fix: int[] next = cost.clone();.
Bug 2: K rounds instead of K + 1
import java.util.*;
public class Main {
static int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
int INF = Integer.MAX_VALUE;
int[] cost = new int[n];
Arrays.fill(cost, INF);
cost[src] = 0;
for (int round = 1; round <= k; round++) {
int[] next = cost.clone();
for (int[] f : flights) {
int u = f[0], v = f[1], price = f[2];
if (cost[u] == INF) continue;
if (cost[u] + price < next[v]) next[v] = cost[u] + price;
}
cost = next;
}
return cost[dst] == INF ? -1 : cost[dst];
}
public static void main(String[] args) {
int[][] ex1 = {{0, 1, 100}, {1, 2, 100}, {2, 0, 100}, {1, 3, 600}, {2, 3, 200}};
int[][] ex2 = {{0, 1, 100}, {1, 2, 100}, {0, 2, 500}};
System.out.println(findCheapestPrice(4, ex1, 0, 3, 1));
System.out.println(findCheapestPrice(3, ex2, 0, 2, 1));
System.out.println(findCheapestPrice(3, ex2, 0, 2, 0));
}
}
-1
500
-1
All three wrong; with k = 0 it does zero rounds and never leaves the source. Fix: round <= k + 1. K stops = K + 1 flights.
Bug 3: no infinity check
import java.util.*;
public class Main {
static int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
int INF = Integer.MAX_VALUE;
int[] cost = new int[n];
Arrays.fill(cost, INF);
cost[src] = 0;
for (int round = 1; round <= k + 1; round++) {
int[] next = cost.clone();
for (int[] f : flights) {
int u = f[0], v = f[1], price = f[2];
if (cost[u] + price < next[v]) next[v] = cost[u] + price;
}
cost = next;
}
return cost[dst] == INF ? -1 : cost[dst];
}
public static void main(String[] args) {
int[][] ex1 = {{0, 1, 100}, {1, 2, 100}, {2, 0, 100}, {1, 3, 600}, {2, 3, 200}};
int[][] ex2 = {{0, 1, 100}, {1, 2, 100}, {0, 2, 500}};
System.out.println(findCheapestPrice(4, ex1, 0, 3, 1));
System.out.println(findCheapestPrice(3, ex2, 0, 2, 1));
System.out.println(findCheapestPrice(3, ex2, 0, 2, 0));
}
}
-2147483449
-2147483549
-2147483549
Integer.MAX_VALUE + 100 overflows to a huge negative number, which looks like the cheapest fare of all, and it spreads. Fix: skip cost[u] == INF, or use long and a smaller infinity.
Negative weights and negative cycles: full Bellman-Ford
Dijkstra's proof needs "every other route can only add cost". A cashback flight (weight -4) breaks that: 0 → 1 (2), 0 → 2 (5), 2 → 1 (-4). Dijkstra settles city 1 at 2 and never looks again; the true cheapest is 5 - 4 = 1.
Without a stop limit, a shortest path never repeats a city, so it uses at most V - 1 edges: V - 1 rounds are always enough (and updating in place is fine, it only finds good paths sooner). If a V-th round still improves something, there is a negative cycle.
import java.util.*;
public class Main {
static int[] dijkstra(int n, int[][] edges, int src) {
List<List<int[]>> adj = new ArrayList<>();
for (int v = 0; v < n; v++) adj.add(new ArrayList<>());
for (int[] e : edges) adj.get(e[0]).add(new int[]{e[1], e[2]});
int[] dist = new int[n];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[src] = 0;
boolean[] settled = new boolean[n];
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[1], b[1]));
pq.add(new int[]{src, 0});
while (!pq.isEmpty()) {
int u = pq.poll()[0];
if (settled[u]) continue;
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];
pq.add(new int[]{e[0], dist[e[0]]});
}
}
return dist;
}
static int[] bellmanFord(int n, int[][] edges, int src) {
int INF = Integer.MAX_VALUE;
int[] dist = new int[n];
Arrays.fill(dist, INF);
dist[src] = 0;
for (int round = 1; round <= n - 1; round++)
for (int[] e : edges)
if (dist[e[0]] != INF && dist[e[0]] + e[2] < dist[e[1]])
dist[e[1]] = dist[e[0]] + e[2];
for (int[] e : edges)
if (dist[e[0]] != INF && dist[e[0]] + e[2] < dist[e[1]])
return null;
return dist;
}
public static void main(String[] args) {
int[][] neg = {{0, 1, 2}, {0, 2, 5}, {2, 1, -4}};
int[][] cyc = {{0, 1, 4}, {1, 2, -3}, {2, 1, 1}};
System.out.println("Dijkstra: " + Arrays.toString(dijkstra(3, neg, 0)));
System.out.println("Bellman-Ford: " + Arrays.toString(bellmanFord(3, neg, 0)));
System.out.println("With a cycle: " + Arrays.toString(bellmanFord(3, cyc, 0)));
}
}
Dijkstra: [0, 2, 5]
Bellman-Ford: [0, 1, 5]
With a cycle: null
Dijkstra (classic, with a settled array) says 2 for city 1; Bellman-Ford says 1. The graph 1 → 2 (-3), 2 → 1 (1) has a loop of total -2, so Bellman-Ford returns null.
Complexity
| Approach | Time | Space | Test |
|---|---|---|---|
| Dijkstra by price | O((V + E) log V) | O(V + E) | wrong: ignores the stop limit (400 instead of 700) |
| Try every route (DFS) | exponential | O(V + E) | 40 cities: Time Limit Exceeded |
| Bellman-Ford, K + 1 rounds | O(K × E) | O(V) | 9,900 flights: a few ms |
| Full Bellman-Ford | O(V × E) | O(V) | handles negative weights, finds negative cycles |
| BFS by stops (practice 3) | O(K × E) | O(V + E) | same answers |
Each round looks at every edge once, so K + 1 rounds cost O(K × E). On big graphs with no stop limit and no negative weights, Dijkstra is faster; Bellman-Ford wins when there is a stop limit or negative weights.
Common mistakes
| Mistake | What you see (real) | Why | Fix |
|---|---|---|---|
| Dijkstra by price only | 400 instead of 700 |
one price per city ignores stops | rounds of flights |
next = cost (no copy) |
400 instead of 700 |
two flights in one round | cost.clone() |
round <= k |
-1, 500, -1 |
K stops = K + 1 flights | round <= k + 1 |
| No ∞ check | -2147483449 |
MAX_VALUE + price overflows |
skip ∞ cities |
| Dijkstra with negative weights | 2 instead of 1 |
a settled price can still drop | Bellman-Ford |
| Ignoring negative cycles | prices that keep dropping | no shortest path exists | check round V |
Mini project: Asha's fare table
The cheapest fare from Delhi to every city, for 0, 1, 2 and 3 layovers, printed as a table (each row is one more Bellman-Ford round, from a copy).
import java.util.*;
public class Main {
// Mini project: Asha's fare table. Cheapest fare from Delhi to every city, for 0, 1, 2 and 3 layovers.
public static void main(String[] args) {
String[] city = {"Delhi", "Jaipur", "Mumbai", "Pune", "Goa"};
int[][] flights = {{0, 1, 2500}, {0, 2, 4500}, {1, 2, 1500}, {1, 3, 3000}, {2, 3, 1200}, {2, 4, 3500}, {3, 4, 1000}, {0, 4, 9000}};
int n = city.length, INF = Integer.MAX_VALUE;
int[] cost = new int[n];
Arrays.fill(cost, INF);
cost[0] = 0;
System.out.printf("%-10s", "layovers");
for (String c : city) System.out.printf("%9s", c);
System.out.println();
for (int round = 1; round <= 4; round++) {
int[] next = cost.clone();
for (int[] f : flights)
if (cost[f[0]] != INF && cost[f[0]] + f[2] < next[f[1]]) next[f[1]] = cost[f[0]] + f[2];
cost = next;
System.out.printf("%-10s", "<= " + (round - 1));
for (int c : cost) System.out.printf("%9s", c == INF ? "-" : String.valueOf(c));
System.out.println();
}
}
}
layovers Delhi Jaipur Mumbai Pune Goa
<= 0 0 2500 4500 - 9000
<= 1 0 2500 4000 5500 8000
<= 2 0 2500 4000 5200 6500
<= 3 0 2500 4000 5200 6200
Each extra layover allowed can only make a fare cheaper or keep it the same. Goa drops from 9,000 (direct) to 6,200 with three layovers.
Practice
1. Network Delay Time (LeetCode 743) with Bellman-Ford.
Solution
No stop limit, so V - 1 rounds updating in place; stop early when a round changes nothing.
import java.util.*;
public class Main {
// Network Delay Time (LeetCode 743) with Bellman-Ford: n - 1 rounds, updating in place (no stop limit).
static int networkDelayTime(int[][] times, int n, int k) {
int INF = Integer.MAX_VALUE;
int[] dist = new int[n + 1];
Arrays.fill(dist, INF);
dist[k] = 0;
for (int round = 1; round <= n - 1; round++) {
boolean changed = false;
for (int[] t : times)
if (dist[t[0]] != INF && dist[t[0]] + t[2] < dist[t[1]]) { dist[t[1]] = dist[t[0]] + t[2]; changed = true; }
if (!changed) break; // nothing improved: every later round would be the same
}
int ans = 0;
for (int v = 1; v <= n; v++) {
if (dist[v] == INF) 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));
}
}
2
1
-1
2. Print the cheapest route with at most K stops, not just its price.
Solution
Keep one cost row and one parent row per round. Walk back from dst: if the price in round r came from round r - 1 unchanged, step to the earlier round; otherwise follow the parent.
import java.util.*;
public class Main {
// Print the cheapest route with at most k stops: keep a parent per round, then walk back.
public static void main(String[] args) {
int n = 4, src = 0, dst = 3, k = 1, INF = Integer.MAX_VALUE;
int[][] flights = {{0, 1, 100}, {1, 2, 100}, {2, 0, 100}, {1, 3, 600}, {2, 3, 200}};
int[][] cost = new int[k + 2][n], par = new int[k + 2][n];
for (int[] row : cost) Arrays.fill(row, INF);
for (int[] row : par) Arrays.fill(row, -1);
cost[0][src] = 0;
for (int r = 1; r <= k + 1; r++) {
for (int v = 0; v < n; v++) { cost[r][v] = cost[r - 1][v]; par[r][v] = -2; } // -2: same as last round
for (int[] f : flights)
if (cost[r - 1][f[0]] != INF && cost[r - 1][f[0]] + f[2] < cost[r][f[1]]) {
cost[r][f[1]] = cost[r - 1][f[0]] + f[2];
par[r][f[1]] = f[0];
}
}
List<Integer> route = new ArrayList<>();
int v = dst, r = k + 1;
while (r > 0) {
if (par[r][v] == -2) { r--; continue; }
route.add(v); v = par[r][v]; r--;
}
route.add(v);
Collections.reverse(route);
System.out.println("cost " + cost[k + 1][dst] + ", route " + route);
}
}
cost 700, route [0, 1, 3]
3. Solve LeetCode 787 with BFS by number of stops.
Solution
BFS level = number of flights taken. Process at most k + 1 levels and only push a city when its cost improves.
import java.util.*;
public class Main {
// LeetCode 787 with BFS by number of stops: level = flights taken; keep the cheapest cost seen per city.
static int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
List<List<int[]>> adj = new ArrayList<>();
for (int v = 0; v < n; v++) adj.add(new ArrayList<>());
for (int[] f : flights) adj.get(f[0]).add(new int[]{f[1], f[2]});
int[] best = new int[n];
Arrays.fill(best, Integer.MAX_VALUE);
best[src] = 0;
Deque<int[]> q = new ArrayDeque<>();
q.add(new int[]{src, 0});
for (int level = 0; level <= k && !q.isEmpty(); level++) {
for (int size = q.size(); size > 0; size--) {
int[] cur = q.poll();
for (int[] e : adj.get(cur[0]))
if (cur[1] + e[1] < best[e[0]]) { best[e[0]] = cur[1] + e[1]; q.add(new int[]{e[0], best[e[0]]}); }
}
}
return best[dst] == Integer.MAX_VALUE ? -1 : best[dst];
}
public static void main(String[] args) {
int[][] ex1 = {{0, 1, 100}, {1, 2, 100}, {2, 0, 100}, {1, 3, 600}, {2, 3, 200}};
int[][] ex2 = {{0, 1, 100}, {1, 2, 100}, {0, 2, 500}};
System.out.println(findCheapestPrice(4, ex1, 0, 3, 1));
System.out.println(findCheapestPrice(3, ex2, 0, 2, 1));
System.out.println(findCheapestPrice(3, ex2, 0, 2, 0));
}
}
700
200
500
4. Find a negative cycle and print it.
Solution
Start every distance at 0 (as if a hidden source reached every vertex), run V rounds and remember parents. A vertex updated in round V leads back into a cycle: walk back V parents to land on it, then follow parents until you return.
import java.util.*;
public class Main {
// Find a negative cycle and print it: after n rounds, a vertex updated in round n leads back into the cycle.
public static void main(String[] args) {
int n = 4;
int[][] edges = {{0, 1, 1}, {1, 2, 2}, {2, 3, -6}, {3, 1, 1}};
long[] dist = new long[n]; // all 0: as if a hidden source reaches every vertex with cost 0
int[] par = new int[n];
Arrays.fill(par, -1);
int x = -1;
for (int round = 1; round <= n; round++) {
x = -1;
for (int[] e : edges)
if (dist[e[0]] + e[2] < dist[e[1]]) { dist[e[1]] = dist[e[0]] + e[2]; par[e[1]] = e[0]; x = e[1]; }
}
if (x == -1) { System.out.println("no negative cycle"); return; }
for (int i = 0; i < n; i++) x = par[x]; // walk back n steps: now x is surely on the cycle
List<Integer> cycle = new ArrayList<>();
for (int v = x; ; v = par[v]) { cycle.add(v); if (v == x && cycle.size() > 1) break; }
Collections.reverse(cycle);
System.out.println("negative cycle: " + cycle);
}
}
negative cycle: [3, 1, 2, 3]
The cycle 1 → 2 → 3 → 1 has total 2 - 6 + 1 = -3.
Quick quiz
Flights: 0→1 (50), 1→2 (50), 2→3 (50), 1→3 (300), 0→3 (500); src = 0, dst = 3, k = 1. Cheapest price? A) 150 B) 350 C) 500 D) -1
Answer
B) 350. 0 → 1 → 2 → 3 = 150 needs two stops (1 and 2). With one stop: 0 → 1 → 3 = 50 + 300 = 350, cheaper than the direct 500.
Interview questions
- Why does Dijkstra fail on LeetCode 787? It keeps one best price per city; a costlier route with fewer stops is thrown away, and the stop limit can't be respected.
- Why copy the array each round? So round
i + 1uses only prices reachable iniflights; otherwise one round can chain several flights and break the stop limit. - Why are V - 1 rounds enough without a limit? A shortest path (no negative cycle) never repeats a vertex, so it has at most V - 1 edges, and round
ifixes every path ofiedges. - How do you detect a negative cycle? Run one more round; if any distance still improves, a negative cycle is reachable.
- Complexity? O(K × E) with a stop limit, O(V × E) for full Bellman-Ford; O(V) space.
- Dijkstra or Bellman-Ford? Dijkstra for non-negative weights and big graphs (O((V + E) log V)); Bellman-Ford for negative weights, stop limits, or cycle detection.
- Why can
INF + pricebe a bug in Java but not in Python? Java'sintoverflows and wraps around; Python'sfloat("inf") + 100stays infinity.
Glossary
| Term | Meaning |
|---|---|
| Weighted directed edge | A one-way link u → v with a number (weight) on it |
| Stop (layover) | A city in between, not the source and not the destination |
| K stops | At most K + 1 flights (edges) |
| Relax | Improve cost[v] through u if cost[u] + w is smaller |
| Round | One pass relaxing every edge once |
| Bellman-Ford | Shortest paths by rounds of relaxing every edge |
| Copy per round | Each round reads only the previous round's prices |
| Negative weight | A weight below 0 (a cashback) |
| Negative cycle | A loop whose total weight is below 0 |
| Infinity | "Not reachable yet"; here Integer.MAX_VALUE |
| Integer overflow | An int past 2147483647 wraps to a negative number |
| O(K × E) | K + 1 rounds, each over E edges |
Summary
- K stops = K + 1 flights. Dijkstra keeps one price per city, so it can't respect a stop limit; trying every route is exponential.
- Bellman-Ford with a limit: K + 1 rounds, each relaxing every flight from a copy of the last round: O(K × E) time, O(V) space.
- Full Bellman-Ford: V - 1 rounds handle negative weights; a V-th round that still improves means a negative cycle.
- Watch for: no copy, one round short, and
INF + priceoverflow. - Next episode: Floyd-Warshall, the shortest path between every pair of cities.