Cheapest Flights Within K Stops medium

Problem Statement

You are given a graph where each edge has a weight associated with it. The graph is represented using an adjacency matrix where flights[i] = [from, to, price] indicates a flight from city from to city to with cost price. You are also given three integers: n (number of cities), src (source city), dst (destination city), and k (maximum number of stops allowed).

Find the cheapest price from src to dst with at most k stops. If there is no such route, return -1.

Example 1

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

Output: 200

Explanation: The cheapest price from city 0 to city 2 with at most 1 stop costs 200, as depicted in the figure.

Example 2

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

Output: 500

Explanation: The cheapest price from city 0 to city 2 with at most 0 stop costs 500.

Steps

1. Initialization: Create a distance array dist of size n filled with infinity, except for dist[src] = 0. Also, create a priority queue pq to store (cost, city, stops) tuples, initialized with (0, src, 0).

2. Dijkstra's Algorithm with Stops: While the priority queue is not empty:

   • Pop the tuple with the lowest cost from the priority queue.
   • If we've reached the destination, return the cost.
   • If the number of stops exceeds k, continue to the next iteration.
   • Iterate through the edges:
     • If an edge starts at the current city, update the distance to the destination city if a cheaper path is found.
     • Add the new (cost, destination city, stops + 1) tuple to the priority queue.

3. No Path Found: If the loop completes without finding the destination, return -1.

Explanation

This problem is a variation of the shortest path problem, specifically Dijkstra's algorithm. The key addition here is the constraint on the number of stops (k). We use a priority queue to efficiently explore the graph, prioritizing nodes with lower costs. The stops variable in each tuple ensures we don't exceed the allowed number of stops. The use of a priority queue (min-heap) guarantees that we always explore the cheapest paths first, leading to an optimal solution.

Code

import heapq

def findCheapestPrice(n, flights, src, dst, k):
    """
    Finds the cheapest price from src to dst with at most k stops.

    Args:
        n: The number of cities.
        flights: A list of lists, where each inner list represents a flight [from, to, price].
        src: The source city.
        dst: The destination city.
        k: The maximum number of stops allowed.

    Returns:
        The cheapest price, or -1 if no such route exists.
    """

    graph = collections.defaultdict(list)
    for u, v, w in flights:
        graph[u].append((v, w))

    dist = [float('inf')] * n
    dist[src] = 0
    pq = [(0, src, 0)] # (cost, city, stops)

    while pq:
        cost, city, stops = heapq.heappop(pq)

        if city == dst:
            return cost

        if stops > k:
            continue

        for neighbor, weight in graph[city]:
            new_cost = cost + weight
            if new_cost < dist[neighbor]:
                dist[neighbor] = new_cost
                heapq.heappush(pq, (new_cost, neighbor, stops + 1))

    return -1

import collections

Complexity

• Time Complexity: O(E log V), where E is the number of edges and V is the number of vertices (cities). This is due to the use of Dijkstra's algorithm with a priority queue.
• Space Complexity: O(V + E), primarily for the adjacency list representation of the graph and the distance array. The priority queue also contributes to space complexity but it is bounded by the number of edges in the worst case.