algoadvance

You are given a set of flights, each represented as a tuple (source, destination, price), and you’re tasked with finding the cheapest price from a given starting city src to a destination city dst with at most K stops in between. If no such route exists, return -1.

Clarifying Questions

  1. Are negative weights allowed?
    • No, all prices are positive integers.
  2. Can there be multiple flights between the same pair of cities?
    • Yes, there can be multiple flights between the same pair of cities with different prices.
  3. Are the cities indexed or named?
    • Cities are indexed as integers starting from 0 up to n-1 where n is the number of cities.
  4. What if src equals dst?
    • If src equals dst, the cheapest price is 0 since no travel is required.

Strategy

To solve this problem, we can use a variation of Dijkstra’s algorithm which also takes into account the number of stops. However, a more straightforward approach is to use Breadth-First Search (BFS) with a priority queue (min-heap) to always extend the least costly route first.

  1. Graph Representation: Represent flights as an adjacency list where each node points to a list of (destination, price) pairs.
  2. Priority Queue: Use a priority queue to explore the least expensive route first.
  3. Tracking Stops: Maintain a record of the number of stops made so far to ensure it does not exceed K.

Code

import heapq
from collections import defaultdict, deque
from typing import List, Tuple

def findCheapestPrice(n: int, flights: List[Tuple[int, int, int]], src: int, dst: int, K: int) -> int:
    # Build the graph
    graph = defaultdict(list)
    for u, v, price in flights:
        graph[u].append((v, price))
    
    # Min-heap priority queue
    pq = [(0, src, 0)]  # (cost, current_city, stops)
    
    # Minimum cost to a node within K stops
    dist = {}
    
    while pq:
        cost, u, stops = heapq.heappop(pq)
        
        # If we've reached the destination city
        if u == dst:
            return cost
        
        # If we have more stops available
        if stops <= K:
            for v, price in graph[u]:
                new_cost = cost + price
                
                # Only consider this new path if it offers a cheaper price
                # or we haven't seen this node with <= stops before
                if new_cost < dist.get((v, stops), float('inf')):
                    dist[(v, stops)] = new_cost
                    heapq.heappush(pq, (new_cost, v, stops+1))
    
    return -1

# Example Use-case
n = 5
flights = [(0, 1, 100), (1, 2, 100), (2, 0, 100), (1, 3, 600), (2, 3, 200)]
src = 0
dst = 3
K = 1
print(findCheapestPrice(n, flights, src, dst, K))  # Output: 700

Time Complexity

Thus, the overall time complexity is O((V + E) log(V)). This complexity is efficient for reasonable numbers of cities and flights.

Try our interview co-pilot at AlgoAdvance.com