Definition
- Bounded-hop shortest path – find the cheapest path from source to destination using at most K stops (K+1 edges).
- Bellman-Ford relaxation – for each edge (u, v, price), update cost[v] = min(cost[v], snapshot[u] + price) if snapshot[u] is not infinity.
- Snapshot trick – copy the cost array before each round so relaxations read from the previous round's values, preventing multi-hop chaining within a single round.
- K+1 rounds – K stops means K+1 edges; each round allows one more edge, so K+1 rounds cover all allowed paths.
- Why not Dijkstra – Dijkstra greedily settles nodes and has no natural way to respect a hard hop limit.
The National Bank of India routes international wires through correspondent banks, where each hop charges a fee. Regulation caps the number of intermediate banks at K. Rajesh wants the cheapest route that uses no more than K hops, so he uses bounded Bellman-Ford to find it.
Understanding the Concepts
What is the Cheapest Flights Within K Stops problem?
The problem gives n cities, a list of flights as (source, destination, price), a source city, a destination city, and a maximum number of stops K. The task is to find the cheapest total price to fly from source to destination using at most K intermediate stops. If no such route exists, return -1.
package com.bank.service;
import java.util.Arrays;
public class CheapestFlightsKStops {
public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
int[] cost = new int[n];
Arrays.fill(cost, Integer.MAX_VALUE);
cost[src] = 0;
for (int round = 0; round <= k; round++) {
int[] snapshot = cost.clone(); // freeze previous round
for (int[] flight : flights) {
int u = flight[0], v = flight[1], price = flight[2];
if (snapshot[u] != Integer.MAX_VALUE
&& snapshot[u] + price < cost[v]) {
cost[v] = snapshot[u] + price;
}
}
}
return cost[dst] == Integer.MAX_VALUE ? -1 : cost[dst];
}
public static void main(String[] args) {
int[][] flights = {{0,1,100}, {1,2,100}, {0,2,500}};
CheapestFlightsKStops solver = new CheapestFlightsKStops();
System.out.println("Cheapest (k=1): " + solver.findCheapestPrice(3, flights, 0, 2, 1));
System.out.println("Cheapest (k=0): " + solver.findCheapestPrice(3, flights, 0, 2, 0));
}
}
Cheapest (k=1): 200
Cheapest (k=0): 500
Why is the snapshot crucial?
Without the snapshot, relaxations within a single round can chain together. If edge A relaxes city X, and then edge B reads the updated X to relax city Y, both hops happen in one round, violating the one-hop-per-round guarantee. The snapshot freezes the previous round's costs so all relaxations in the current round read from the same frozen state, ensuring each round adds exactly one hop.
package com.bank.service;
import java.util.Arrays;
public class SnapshotImportance {
public static void main(String[] args) {
// Without snapshot: round 1 relaxes 0->1 (cost[1]=100),
// then relaxes 1->2 using the just-updated cost[1]=100
// => cost[2]=200 in ONE round (two hops telescoped)
//
// With snapshot: round 1 reads snapshot[1]=INF,
// so 1->2 is not relaxed (cannot chain)
// Round 2 reads snapshot[1]=100 from round 1, relaxes 1->2 to 200
System.out.println("Snapshot prevents multi-hop chaining in one round.");
System.out.println("Without snapshot: k=0 might give a 2-hop answer.");
}
}
Why K+1 rounds instead of K?
K stops means K intermediate cities, which means K+1 edges (flights). The source does not count as a stop. After round 1, the cost array reflects paths of at most 1 edge. After round r, it reflects paths of at most r edges. So K+1 rounds cover paths of at most K+1 edges, which is the maximum allowed.
package com.bank.service;
public class WhyKPlusOne {
// Path: src -> stop1 -> stop2 -> ... -> stopK -> dst
// Edges: 1 2 K K+1
// So K stops = K+1 edges = K+1 rounds of relaxation
public static void main(String[] args) {
System.out.println("K=0 stops: 1 edge (direct flight)");
System.out.println("K=1 stop: 2 edges (one layover)");
System.out.println("K=2 stops: 3 edges (two layovers)");
}
}
How is this different from standard Bellman-Ford and Dijkstra?
| Feature | Standard Bellman-Ford | Bounded Bellman-Ford | Dijkstra |
|---|---|---|---|
| Rounds | V-1 | K+1 | N/A (priority queue) |
| Snapshot | not needed | required | N/A |
| Hop limit | no | yes (exactly K stops) | hard to enforce |
| Negative weights | handles | handles | cannot handle |
| Time | O(V * E) | O(K * E) | O((V+E) log V) |
package com.bank.service;
public class AlgorithmComparison {
public static void main(String[] args) {
System.out.println("Standard Bellman-Ford: V-1 rounds, no hop limit.");
System.out.println("Bounded Bellman-Ford: K+1 rounds with snapshot.");
System.out.println("Dijkstra: no natural hop limit, greedy settlement.");
}
}
What are the edge cases?
Edge cases include K=0 (only direct flights allowed), no path within K stops (return -1), source equals destination (cost 0), and multiple paths with different costs and hop counts.
package com.bank.service;
public class FlightsEdgeCases {
public static void main(String[] args) {
CheapestFlightsKStops solver = new CheapestFlightsKStops();
// No path within K stops
int[][] flights = {{0,1,100}, {1,2,100}};
System.out.println("No direct (k=0): "
+ solver.findCheapestPrice(3, flights, 0, 2, 0));
// Source equals destination
System.out.println("Same city: "
+ solver.findCheapestPrice(3, flights, 0, 0, 0));
}
}
No direct (k=0): -1
Same city: 0
What are common mistakes?
The most common mistake is relaxing in place without the snapshot, which allows multiple hops in a single round and violates the K-stop constraint. Another mistake is running only K rounds instead of K+1, which misses paths that use exactly K+1 edges.
Wrong code:
// WRONG: no snapshot, multi-hop chaining in one round
for (int round = 0; round <= k; round++) {
for (int[] f : flights) {
if (cost[f[0]] != INF && cost[f[0]] + f[2] < cost[f[1]]) {
cost[f[1]] = cost[f[0]] + f[2]; // reads live values, not snapshot
}
}
}
Correct code:
// CORRECT: snapshot prevents chaining
for (int round = 0; round <= k; round++) {
int[] snap = cost.clone();
for (int[] f : flights) {
if (snap[f[0]] != INF && snap[f[0]] + f[2] < cost[f[1]]) {
cost[f[1]] = snap[f[0]] + f[2]; // reads frozen snapshot
}
}
}
Can you solve it with modified Dijkstra?
Yes, but with care. Use a priority queue with entries (cost, city, stopsUsed). For each entry, explore neighbours only if stopsUsed < K. However, the standard Dijkstra optimisation of skipping already-settled nodes does not work here because a node might be reached with fewer stops later, which opens new paths. This makes the modified Dijkstra less clean than the Bellman-Ford approach.
package com.bank.service;
import java.util.*;
public class CheapestFlightsDijkstra {
public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
List<int[]>[] adj = new List[n];
for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();
for (int[] f : flights) adj[f[0]].add(new int[]{f[1], f[2]});
// {cost, city, stops}
PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
pq.offer(new int[]{0, src, 0});
int[] bestStops = new int[n];
Arrays.fill(bestStops, Integer.MAX_VALUE);
while (!pq.isEmpty()) {
int[] curr = pq.poll();
int cost = curr[0], city = curr[1], stops = curr[2];
if (city == dst) return cost;
if (stops > k || stops >= bestStops[city]) continue;
bestStops[city] = stops;
for (int[] next : adj[city]) {
pq.offer(new int[]{cost + next[1], next[0], stops + 1});
}
}
return -1;
}
public static void main(String[] args) {
int[][] flights = {{0,1,100},{1,2,100},{0,2,500}};
System.out.println("Dijkstra (k=1): "
+ new CheapestFlightsDijkstra().findCheapestPrice(3, flights, 0, 2, 1));
}
}
Dijkstra (k=1): 200
What should a senior engineer know?
A senior engineer knows that the Bellman-Ford approach is O(K * E) and the Dijkstra approach can degenerate to O(V * E * log V) in the worst case because of duplicate queue entries. They prefer the Bellman-Ford approach for its simplicity and predictable performance. In production at National Bank of India, the wire routing service uses bounded Bellman-Ford to find the cheapest compliant route through correspondent banks, with the fee graph cached in Redis and the K limit set by regulation.
package com.bank.service;
public class SeniorFlightsNotes {
public static void main(String[] args) {
System.out.println("Senior insights:");
System.out.println(" Bellman-Ford: O(K*E), simple, predictable.");
System.out.println(" Dijkstra: can degenerate, less clean with hop limit.");
System.out.println(" Snapshot is the key correctness detail.");
System.out.println(" Production: fee graph in Redis, K from regulation.");
}
}
Visual Overview
Cheapest Flights: Bellman-Ford with Snapshot
Flights: 0->1 ($100), 1->2 ($100), 0->2 ($500)
K = 1 stop => 2 rounds
Initial: cost = [0, INF, INF]
Round 1 (snapshot = [0, INF, INF]):
0->1: snap[0]=0 + 100 < INF => cost[1] = 100
1->2: snap[1]=INF => skip (snapshot is frozen!)
0->2: snap[0]=0 + 500 < INF => cost[2] = 500
cost = [0, 100, 500]
Round 2 (snapshot = [0, 100, 500]):
0->1: snap[0]=0 + 100 = 100, not < 100 => skip
1->2: snap[1]=100 + 100 = 200 < 500 => cost[2] = 200
0->2: snap[0]=0 + 500 = 500, not < 200 => skip
cost = [0, 100, 200]
Result: cost[2] = 200 (route 0->1->2, 1 stop)
Without snapshot (WRONG):
Round 1: 0->1 sets cost[1]=100,
1->2 reads cost[1]=100 (live!) => cost[2]=200
That's 2 hops in 1 round! Violates K=0 constraint.
Key Takeaway
Cheapest Flights Within K Stops is a bounded-hop shortest path problem solved with Bellman-Ford style relaxation. The key difference from standard Bellman-Ford is the snapshot: before each round, copy the cost array and relax all edges against the frozen copy. This guarantees each round adds exactly one hop, so after K+1 rounds the destination cost reflects the cheapest route using at most K stops.
Without the snapshot, relaxations within a single round can chain together: one edge updates a city's cost, and another edge reads that updated cost to relax further, telescoping multiple hops into one round. This violates the hop constraint and gives incorrect answers for small K values.
Dijkstra can be adapted with a priority queue carrying (cost, city, stopsUsed), but it loses the standard optimisation of skipping settled nodes because a node might be reachable with fewer stops later. The Bellman-Ford approach is simpler, predictable at O(K * E), and the recommended answer for interviews.
At National Bank of India, Rajesh uses this for international wire routing through correspondent banks. Each hop charges a fee and regulation caps the number of intermediate banks. The fee graph is cached in Redis and the bounded relaxation picks the cheapest compliant route. Explaining the snapshot trick, the K+1 rounds, and why Dijkstra is less natural under a hop limit is what shows an interviewer you understand this bounded shortest path technique.
Remember one sentence: clone the cost array before each round so relaxations read from a frozen snapshot, run K+1 rounds, and the destination cost is the cheapest path within K stops.
---