Cheapest Flights Within K Stops

medium graph dp bfs shortest path

Problem

n cities and flights[i] = [from, to, price]. Find the cheapest price from src to dst using at most K stops (so K + 1 edges). Return −1 if no such route exists.

Inputflights = [[0,1,100],[1,2,100],[0,2,500]], n = 3, src = 0, dst = 2, K = 1

Output200

0 → 1 → 2 has 1 stop and total cost 200; cheaper than the direct 500.

flights (u,v,w; …)

src

dst

def find_cheapest_price(n, flights, src, dst, K):
    INF = float('inf')
    dist = [INF] * n
    dist[src] = 0
    for _ in range(K + 1):
        snap = dist[:]
        for u, v, w in flights:
            if snap[u] + w < dist[v]:
                dist[v] = snap[u] + w
    return -1 if dist[dst] == INF else dist[dst]

function findCheapestPrice(n, flights, src, dst, K) {
  const INF = Infinity;
  let dist = new Array(n).fill(INF);
  dist[src] = 0;
  for (let i = 0; i <= K; i++) {
    const snap = dist.slice();
    for (const [u, v, w] of flights) {
      if (snap[u] + w < dist[v]) dist[v] = snap[u] + w;
    }
  }
  return dist[dst] === INF ? -1 : dist[dst];
}

class Solution {
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {
        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[src] = 0;
        for (int i = 0; i <= K; i++) {
            int[] snap = dist.clone();
            for (int[] e : flights) {
                if (snap[e[0]] == Integer.MAX_VALUE) continue;
                if (snap[e[0]] + e[2] < dist[e[1]]) dist[e[1]] = snap[e[0]] + e[2];
            }
        }
        return dist[dst] == Integer.MAX_VALUE ? -1 : dist[dst];
    }
}

class Solution {
public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int K) {
        const int INF = INT_MAX;
        vector<int> dist(n, INF);
        dist[src] = 0;
        for (int i = 0; i <= K; i++) {
            vector<int> snap = dist;
            for (auto& e : flights) {
                if (snap[e[0]] == INF) continue;
                if (snap[e[0]] + e[2] < dist[e[1]]) dist[e[1]] = snap[e[0]] + e[2];
            }
        }
        return dist[dst] == INF ? -1 : dist[dst];
    }
};

Explanation

We want the cheapest fare from src to dst using at most K stops, meaning at most K+1 flights. The clean way is Bellman-Ford, run for exactly K+1 rounds so the path length stays limited.

We keep a dist array of the cheapest known cost to each city, starting at 0 for the source and infinity elsewhere. Each round we relax every flight: if reaching u then flying u→v is cheaper than the current dist[v], we update it.

The subtle but crucial detail is the snap snapshot. Each round relaxes using last round's distances, not the values being updated mid-round. This guarantees that after round i, dist reflects the best price reachable with at most i flights — so we never sneak in extra hops beyond the limit.

Example: flights=[[0,1,100],[1,2,100],[0,2,500]], src=0, dst=2, K=1. Round 1 sets dist[1]=100 and dist[2]=500; round 2 uses the snapshot to find 0→1→2 = 200, beating 500. The answer is 200.

Time: O(K · E) Space: O(n)