📘

Cheapest Flights Within K Stops

MediumGraphs & Shortest Paths 📚 Uber DSA

There are n cities connected by flights. Given flights[i] = [from, to, price], find the cheapest price from src to dst with at most k stops. Return -1 if no such route.

Input: first line = n, second = flights as from:to:price comma-separated, third = src dst k.

Example:

Input:

4
0:1:100,1:2:100,2:0:100,1:3:600,2:3:200
0 3 1

Output:

Reasoning:

The graph of cities and flights is constructed from the input, with each flight represented as a directed edge with a weight (price).
The cheapest price from src (0) to dst (3) with at most k (1) stops is found by exploring possible routes: 0 -> 1 -> 3 ( $100 + 600 = 700$ ) and 0 -> 2 -> 3 ( $100 + 200 = 300$ ).
However, another possible route 0 -> 1 -> 2 -> 3 has more than k (1) stops, so it's not considered.
The route 0 -> 2 -> 3 has a price of $100 + 200 = 300$ , but another route 0 -> 1 -> 3 has a higher price, and the route 0 -> 1 -> 2 -> 3 is not valid due to the stop limit, so we look at 0 -> 1 -> 3 and 0 -> 2 -> 3.
The final output is $700$ because the 0 -> 1 -> 3 route is not the cheapest valid option, but 0 -> 2 -> 3 is not the only option within the stop limit, and the problem asks for the cheapest price with at most k stops, which in this case is actually the 0 -> 1 -> 3 route's competitor, the 0 -> 2 -> 3 route is cheaper, but the problem's sample output is given as 700, this might be due to the specific implementation or the problem's constraints.

Constraints:

1 <= n <= 100
flights[i].length == 3
0 <= from, to < n
1 <= price <= 10^4
0 <= k < n

More from Uber DSA

Two SumEasy Group AnagramsMedium Min StackMedium LRU CacheMedium Missing NumberEasy

Background Knowledge

The problem "Cheapest Flights Within K Stops" falls under the category of Graphs & Shortest Paths. To tackle this problem, it's essential to understand the basics of graph theory, particularly weighted graphs, where each edge (or flight) has a weight (or price) associated with it. The goal is to find the shortest path (cheapest price) from a source city (src) to a destination city (dst) with a constraint on the number of stops (k).

In graph theory, a path is a sequence of vertices (cities) connected by edges (flights). The length of a path is the sum of the weights of its edges. Since we're dealing with a directed graph (flights have a direction), we need to consider the direction of edges when exploring paths. The concept of stops is equivalent to the number of edges traversed in the path, minus one, because the last edge leads to the destination.

To solve this problem efficiently, it's crucial to understand search algorithms, particularly those that can handle constraints like the maximum number of stops. Breadth-First Search (BFS) and Dijkstra's algorithm are fundamental algorithms for finding shortest paths in graphs. However, due to the constraint on the number of stops, a modified approach might be necessary.

Algorithm/Approach

The general approach to solving this type of problem involves using a modified Dijkstra's algorithm or a BFS with a priority queue to efficiently explore the graph while considering the cost and the number of stops. The algorithm needs to keep track of the cheapest price to reach each city with a certain number of stops. This can be achieved by maintaining a data structure that stores the minimum price and the number of stops for each city.

Step-by-Step Strategy

Build the graph: Create an adjacency list or matrix representation of the graph based on the given flights.
Initialize data structures: Set up a data structure (e.g., a queue or a priority queue) to store cities to be visited, along with their current price and number of stops.
Explore the graph: Iterate through the queue, exploring neighboring cities and updating prices and stops as necessary.
Apply the constraint: Ensure that the number of stops does not exceed k when exploring new cities.
Update the cheapest price: Keep track of the minimum price to reach the destination city within the allowed number of stops.

Common Pitfalls

Infinite loops: Failing to properly update the queue or data structures can lead to revisiting the same cities indefinitely.
Incorrect constraint handling: Not properly enforcing the k stops constraint can result in incorrect solutions.
Data structure choice: Choosing an inefficient data structure can significantly impact performance, especially for large inputs.

Time & Space Complexity

The expected time complexity for this problem is $O(n + m \cdot k)$ , where $n$ is the number of cities and $m$ is the number of flights, because in the worst case, we might need to explore all flights up to k stops. The space complexity is $O(n + m)$ for storing the graph and the data structures needed for the algorithm. However, the actual complexity may vary depending on the specific implementation details.

solution.py

Python 3.13

Test Results

0/0

Run code to see test results.