Cheapest Flights Within K Stops

84.5k
0

A network contains n cities numbered from 0 to n-1. Every directed flight [from,to,price] travels from from to to for the listed price.

Given source city src, destination city dst, and integer k, return the cheapest price from source to destination with at most k intermediate stops. Return -1 when no valid route exists. A limit of k stops permits at most k+1 flights.

Example 1

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

Explanation: Route 0->1->3 costs 700 and uses one stop. Route 0->1->2->3 costs 400 but uses two stops, exceeding the limit.

Example 2

Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 0

Output: 500

Explanation: Zero stops permit only a direct flight, so flight 0->2 supplies the valid minimum price.

Approach 1

Bounded Bellman–Ford builds cheapest prices by flight count. After round r, the distance array stores the minimum price using at most r flights. Since K stops allow at most K+1 flights, exactly K+1 rounds cover every valid route.

Each round reads from the previous distance layer and writes into a copy. Separate arrays prevent several flights from chaining within one round.

Algorithm

  • Initialize all city prices as infinity and set the source price to 0, establishing the starting state before taking any flight.

  • Perform exactly K+1 rounds, since a route containing at most K intermediate stops can use at most K+1 flights.

  • Copy the current distance array at the beginning of every round, preserving prices calculated with fewer flights.

  • Traverse every directed flight and skip an edge when the departure city remains unreachable.

  • Calculate the candidate price using the previous distance array and update the arrival city only in the copied array.

  • Replace the distance array with the completed copy after processing all flights, advancing the allowed flight count by one.

  • Return -1 when the destination remains unreachable; otherwise, return the minimum destination price.

Dry Run

cheapest flights 1

cheapest flights 1

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Returns the cheapest price using at most k stops.
long long findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
// Use a wide sentinel outside valid accumulated prices.
const long long INF = numeric_limits<long long>::max() / 4;
// Store prices using a wide integer type.
vector<long long> distance(n, INF);
// Set the zero-flight price for the source city.
distance[src] = 0;
// Build prices using at most k + 1 flights.
for (int used = 0; used <= k; used++) {
vector<long long> nextDistance = distance;
// Relax every directed flight from the previous layer.
for (const vector<int>& flight : flights) {
int from = flight[0];
int to = flight[1];
long long price = flight[2];
// Skip unreachable departure cities.
if (distance[from] == INF) {
continue;
}
// Update only the next flight-count layer.
nextDistance[to] = min(
nextDistance[to],
distance[from] + price
);
}
// Move to the next layer after all flights are relaxed.
distance = nextDistance;
}
// Convert an unreachable destination into -1.
return distance[dst] == INF ? -1 : distance[dst];
}
};
// Driver code.
int main() {
int n = 4;
vector<vector<int>> flights = {
{0, 1, 100}, {1, 2, 100}, {2, 0, 100},
{1, 3, 600}, {2, 3, 200}
};
Solution solution;
cout << solution.findCheapestPrice(n, flights, 0, 3, 1);
return 0;
}

Complexity Analysis

Time Complexity: O((K+1)×E), where K is the stop limit and E is the number of directed flights; every round scans all flights.

Space Complexity: O(N), where N is the number of cities; two wide-integer distance arrays store consecutive flight-count layers.

Approach 2

State-aware Dijkstra treats {flightsUsed, city} as the complete state. Reaching the same city with different flight counts creates different remaining possibilities, so a city-only distance array is insufficient.

A min-heap processes the lowest-cost valid state first. Non-negative flight prices make the first destination state removed from the heap the cheapest valid route.

Algorithm

  • Build a directed weighted adjacency list from all flights, storing each destination city with the corresponding price.

  • Initialize a best table with K+2 flight layers and N cities, where every entry initially contains infinity.

  • Set best[0][source]=0 and insert {0, source, 0} into a min-heap, representing zero price with no flights used.

  • Continue processing while the heap contains states, remove the state having the smallest price, and skip stale entries that differ from the matching table value.

  • Return the current price when the removed city is the destination, as no cheaper valid state remains in the min-heap.

  • When fewer than K+1 flights have been used, relax every outgoing flight into the next layer and insert each improved state into the heap.

  • Return -1 when the heap becomes empty without reaching the destination within the allowed flight count.

Dry Run

cheapest flight 2

cheapest flight 2

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Returns the cheapest price using at most k stops.
long long findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
// Build the directed weighted adjacency list.
vector<vector<pair<int, int>>> adjacency(n);
for (const vector<int>& flight : flights) {
adjacency[flight[0]].push_back({flight[1], flight[2]});
}
// Use a wide sentinel outside valid accumulated prices.
const long long INF = numeric_limits<long long>::max() / 4;
int maxFlights = k + 1;
// Store the best price for every flight-count and city state.
vector<vector<long long>> best(maxFlights + 1, vector<long long>(n, INF));
using State = tuple<long long, int, int>;
// Process states by increasing total price.
priority_queue<State, vector<State>, greater<State>> minHeap;
// Start from source with zero flights and zero price.
best[0][src] = 0;
minHeap.push({0, src, 0});
while (!minHeap.empty()) {
auto [cost, city, used] = minHeap.top();
minHeap.pop();
// Skip states replaced by cheaper matching states.
if (cost != best[used][city]) {
continue;
}
// Destination popped first is the cheapest valid answer.
if (city == dst) {
return cost;
}
// Stop paths exceeding k + 1 flights.
if (used == maxFlights) {
continue;
}
// Relax outgoing flights into the next layer.
for (const auto& [neighbor, price] : adjacency[city]) {
int nextUsed = used + 1;
long long nextCost = cost + price;
// Update only when the new price is cheaper.
if (nextCost < best[nextUsed][neighbor]) {
best[nextUsed][neighbor] = nextCost;
minHeap.push({nextCost, neighbor, nextUsed});
}
}
}
// Return -1 when destination cannot be reached.
return -1;
}
};
// Driver code.
int main() {
int n = 4;
vector<vector<int>> flights = {
{0, 1, 100}, {1, 2, 100}, {2, 0, 100},
{1, 3, 600}, {2, 3, 200}
};
Solution solution;
cout << solution.findCheapestPrice(n, flights, 0, 3, 1);
return 0;
}

Complexity Analysis

Time Complexity: O((K+1)×E×log((K+2)×N)), where N is the city count, E is the flight count, and K is the stop limit. Heap operations introduce a logarithmic factor, so bounded Bellman–Ford has the better worst-case asymptotic bound.
Space Complexity: O((K+2)×N+(K+1)×E), where the layered state table stores city prices, while the adjacency list and heap store flight transitions.

Interview follow-up Questions

Stops count only intermediate cities. A route containing one intermediate city contains two flight edges.

Graph

Read Similar Blogs

Graph

Disjoint Set Union: Union by Rank, Size and Path Compression

Design a disjoint set, also called a union-find data structure, for N nodes numbered from 1 to N . Initially, every node belongs to a separate set. Support the following operations: D...

89.1k
Graph

Dijkstra’s Algorithm

Given an undirected weighted graph with V vertices numbered from 0 to V - 1 , an edge list, and a source vertex, find the shortest distance from source to every vertex. Every edge appears as [u, v,...

93k
Graph

Print Shortest Path

Given a weighted undirected graph with n vertices numbered from 1 to n and m edges, find a shortest path from vertex 1 to vertex n . Each edge appears as [u, v, weight] and every weight is positive...

96.1k
Comments0