SyntaxPilot
Courses/DSA and Coding Problems/Lesson 53
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 53 of 90

Bellman-Ford and cheapest flights within K stops

queued

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 → v with a number on it, its weight (here a price).
  • Stop: a city you pass through. A route with f flights has f - 1 stops, so K stops = K + 1 flights.
  • Relaxing an edge u → v, w: if reaching u plus w is cheaper than what we know for v, update v.
  • Round: one pass that relaxes every edge once. After round i (from copies), cost[v] is the cheapest price using at most i edges.
  • 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 int that goes past 2147483647 wraps 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.

  1. Round 0: cost[src] = 0, every other city ∞.
  2. Round i + 1: start from a copy of round i's prices and relax every flight using only round i's prices. Now cost[v] = cheapest price with at most i + 1 flights.
  3. 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

  1. 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.
  2. Why copy the array each round? So round i + 1 uses only prices reachable in i flights; otherwise one round can chain several flights and break the stop limit.
  3. 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 i fixes every path of i edges.
  4. How do you detect a negative cycle? Run one more round; if any distance still improves, a negative cycle is reachable.
  5. Complexity? O(K × E) with a stop limit, O(V × E) for full Bellman-Ford; O(V) space.
  6. 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.
  7. Why can INF + price be a bug in Java but not in Python? Java's int overflows and wraps around; Python's float("inf") + 100 stays 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 + price overflow.
  • Next episode: Floyd-Warshall, the shortest path between every pair of cities.