We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Cheapest Flights Within K Stops

Difficulty: Medium

Problem Description

Given n cities connected by some flights, represented as an array where each entry specifies a flight's origin, destination, and cost, the task is to determine the cheapest price to travel from a source city to a destination city with at most k stops. If no such route exists, return -1.

Key Insights

  • The problem can be viewed as a graph traversal problem where cities are nodes and flights are directed edges with weights (costs).
  • A breadth-first search (BFS) approach is suitable for this problem since it allows us to explore all possible flights while keeping track of the number of stops.
  • We need to maintain a priority queue to always expand the least costly path first.
  • Using a distance array to keep track of the minimum cost to reach each city helps in optimizing the search.

Space and Time Complexity

Time Complexity: O(E + V log V), where E is the number of edges (flights) and V is the number of cities. The log V factor comes from the priority queue operations. Space Complexity: O(V), for storing the distances and the graph representation.

Solution

The solution employs a graph representation using an adjacency list and uses a priority queue (min-heap) to explore paths. The algorithm proceeds as follows:

  1. Build the graph from the flights data.
  2. Use a priority queue to explore the cheapest paths, starting from the source city.
  3. For each city, push its neighbors into the queue with updated costs, ensuring that we do not exceed the allowed number of stops.
  4. If we reach the destination city, we return the cost; if the queue is exhausted without finding a path, we return -1.

Code Solutions

import heapq

def findCheapestPrice(n, flights, src, dst, k):
    graph = {i: [] for i in range(n)}
    for u, v, price in flights:
        graph[u].append((v, price))
    
    pq = [(0, src, 0)]  # (cost, current city, stops)
    while pq:
        cost, city, stops = heapq.heappop(pq)
        if city == dst:
            return cost
        if stops <= k:
            for neighbor, price in graph[city]:
                heapq.heappush(pq, (cost + price, neighbor, stops + 1))
    
    return -1
← Back to All Questions