Leetcode 787. Cheapest Flights Within K Stops

We are given n cities and a list of flights (from, to, price). Starting from src, we want the cheapest price to reach dst with at most k stops, equivalently, using at most k + 1 edges.

This is a shortest-path problem with a hard cap on the number of edges. Dijkstra does not naturally enforce that cap, and it also cannot handle negative edge weights. Bellman–Ford fits both needs: it relaxes edges in passes, and after i passes every shortest path that uses at most i edges has been found.

Bellman–Ford

In a graph with v nodes, any simple path has at most v - 1 edges: a longer path would have to repeat a vertex. Bellman–Ford uses this bound. It repeatedly relaxes every edge, and after v - 1 passes the distance to every reachable node is final — unless a negative cycle is reachable from the source, in which case shortest paths are not well-defined.

After the $i$-th complete pass over all edges, every shortest path that uses at most $i$ edges has been correctly accounted for.

Why this invariant holds

Initially,

so the shortest path using $0$ edges — the path from the source to itself — is known.

Suppose after $i - 1$ passes, distances are correct for shortest paths using at most $i - 1$ edges.

Consider a shortest path to $v$ using $i$ edges:

The prefix from $s$ to $u$ uses $i - 1$ edges, so by the previous pass, $d[u]$ is correct. During the next pass, Bellman–Ford relaxes $u \to v$:

Therefore, after pass $i$, paths using $i$ edges have been propagated.

Runtime: $O(VE)$.

Why layer-by-layer relaxation?

The standard Bellman–Ford updates the dist array in place. That is fine when we relax v - 1 times, because we eventually want every reachable path length. But if we want to limit the number of relaxations, as in this problem, where we only allow k + 1 edges, we must copy the array first. Otherwise, the order in which we traverse edges can leak updates from the current pass into later edges of the same pass, effectively exploring more than one new edge at a time.

To see why, consider this graph:

flowchart LR
  A((A)) -->|10| B((B))
  A -->|15| C((C))
  B -->|-5| C

Edges:

• $A \to B$ with weight $10$
• $A \to C$ with weight $15$
• $B \to C$ with weight $-5$

Suppose we start with $d[A] = 0$ and perform a single in-place pass. If we relax $A \to B$ first, then $B \to C$, we get:

1. $d[B] = 10$
2. $d[C] = d[B] + (-5) = 5$

In one pass we have used the path $A \to B \to C$, which has two edges. The order of traversing edges mattered, and we overshot a one-edge budget. With a separate next array that only reads from the previous layer’s dist, $B \to C$ cannot see the fresh $d[B]$ until the next iteration, so each pass truly advances by at most one edge.

Solution

class Solution {
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        final int INF = Integer.MAX_VALUE;
        int[] dist = new int[n];
        Arrays.fill(dist, INF);
        dist[src] = 0;
        for (int i = 0; i < k + 1; i++) { // k + 1 edge relaxations
            // layer-by-layer relaxation instead of in-place relaxation
            // to limit the level, we need a new dist array
            // so that the order of traversing the edges doesn't matter
            int[] next = dist.clone();
            boolean changed = false;
            for (int[] edge : flights) {
                int from = edge[0], to = edge[1], w = edge[2];
                // Integer.MAX_VALUE > Integer.MAX_VALUE + 100 -> overflows
                if (dist[from] == INF) continue;
                if (next[to] > dist[from] + w) {
                    next[to] = dist[from] + w;
                    changed = true;
                }
            }
            dist = next;
            if (!changed) break;
        }
        return dist[dst] == INF ? -1 : dist[dst];
    }
}