Cheapest Flights Within K Stops
Problem Statement
There are n cities connected by flights. Each flight [from, to, price] has a cost. Given a source, destination, and maximum number of stops K, find the cheapest flight from source to destination with at most K stops. If no such route exists, return -1.
Example:
- Input:
n = 4, flights = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], src = 0, dst = 3, K = 1 - Output:
700(Path: 0 → 1 → 3)
Noob-Friendly Explanation
You want to fly from one city to another as cheaply as possible, but you can only make at most K layovers (stops). It's like searching for cheap flights on Google Flights where you set a limit on the number of connections.
Imagine checking every possible route with at most K stops and picking the cheapest one. The smart way uses a modified Bellman-Ford: relax edges K+1 times (K stops means K+1 edges).
Approach 1: Brute Force (DFS)
Intuition
Use DFS to explore all paths from source to destination with at most K+1 edges. Track the minimum cost found.
Algorithm
- Build an adjacency list.
- DFS from source. Track current cost and remaining stops.
- If destination reached, update minimum cost.
- Prune branches where cost exceeds the current best.
import java.util.*;
public class CheapestFlightsBrute {
static int minCost;
public static int findCheapest(int n, int[][] flights, int src, int dst, int K) {
Map<Integer, List<int[]>> adj = new HashMap<>();
for (int i = 0; i < n; i++) adj.put(i, new ArrayList<>());
for (int[] f : flights) {
adj.get(f[0]).add(new int[]{f[1], f[2]});
}
minCost = Integer.MAX_VALUE;
boolean[] visited = new boolean[n];
visited[src] = true;
dfs(adj, src, dst, K + 1, 0, visited);
return minCost == Integer.MAX_VALUE ? -1 : minCost;
}
static void dfs(Map<Integer, List<int[]>> adj, int curr, int dst,
int remainingEdges, int cost, boolean[] visited) {
if (curr == dst) {
minCost = Math.min(minCost, cost);
return;
}
if (remainingEdges == 0) return;
if (cost >= minCost) return; // prune
for (int[] edge : adj.get(curr)) {
int next = edge[0], price = edge[1];
if (!visited[next]) {
visited[next] = true;
dfs(adj, next, dst, remainingEdges - 1, cost + price, visited);
visited[next] = false;
}
}
}
public static void main(String[] args) {
int n = 4;
int[][] flights = {{0,1,100},{1,2,100},{2,0,100},{1,3,600},{2,3,200}};
System.out.println("Cheapest: " + findCheapest(n, flights, 0, 3, 1));
}
}Complexity Analysis
- Time Complexity: O(V^K) - in worst case, each stop branches to V cities
- Space Complexity: O(V) - for visited array and recursion stack
Approach 2: Optimal (Bellman-Ford with K+1 Relaxations)
Intuition
Modified Bellman-Ford: instead of V-1 relaxation rounds, do only K+1 rounds (since K stops means at most K+1 edges). In each round, use the distances from the PREVIOUS round to avoid using edges from the current round (this prevents using more edges than allowed).
Algorithm
- Initialize
dist[src] = 0, all others = infinity. - Repeat K+1 times:
a. Copy the current distances to a temp array.
b. For each flight (u, v, w), if
temp[u] + w < dist[v], updatedist[v]. - Return
dist[dst]or -1 if still infinity.
import java.util.*;
public class CheapestFlightsOptimal {
public static int findCheapest(int n, int[][] flights, int src, int dst, int K) {
int[] dist = new int[n];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[src] = 0;
// K stops = K+1 edges, so relax K+1 times
for (int i = 0; i <= K; i++) {
int[] temp = Arrays.copyOf(dist, n);
for (int[] flight : flights) {
int u = flight[0], v = flight[1], w = flight[2];
if (dist[u] != Integer.MAX_VALUE && dist[u] + w < temp[v]) {
temp[v] = dist[u] + w;
}
}
dist = temp;
}
return dist[dst] == Integer.MAX_VALUE ? -1 : dist[dst];
}
public static void main(String[] args) {
int n = 4;
int[][] flights = {{0,1,100},{1,2,100},{2,0,100},{1,3,600},{2,3,200}};
System.out.println("Cheapest: " + findCheapest(n, flights, 0, 3, 1));
}
}Complexity Analysis
- Time Complexity: O(K * E) - K+1 relaxation rounds, each processing all E edges
- Space Complexity: O(V) - for the distance array (temp copy is also O(V))