Cheapest Flights Within K Stops

 

Problem Description: Given a directed, weighted graph representing flights between cities, along with the source city, destination city, and the maximum number of stops allowed (K), find the cheapest price to reach the destination city within K stops. If it's not possible to reach the destination within K stops, return -1.

Example:

python
# Example usage of the function
n = 3  # Number of cities
flights = [[0,1,100],[1,2,100],[0,2,500]]  # Flights [src, dst, price]
src = 0  # Source city
dst = 2  # Destination city
k = 1  # Maximum number of stops
result = findCheapestPrice(n, flights, src, dst, k)
# The cheapest price to reach city 2 from city 0 within 1 stop is 200

1. Clarify the problem: Before starting, let's ask some clarifying questions to ensure we fully understand the problem requirements:

  • Can the number of cities (n) be 0 or negative?
  • Can the source city (src) or destination city (dst) be out of range (i.e., not between 0 and n-1)?
  • Can the maximum number of stops (k) be negative or zero?
  • Can there be multiple flights between the same source and destination cities?

2. Analyze the problem: Let's break down the problem to better understand its components:

  • Input:
    • The number of cities (n).
    • A list of flights (flights), where each flight is represented as [src, dst, price].
    • The source city (src) and destination city (dst).
    • The maximum number of stops allowed (k).
  • Output: The cheapest price to reach the destination city within k stops. If it's not possible, return -1.
  • Constraints: The source and destination cities will be valid and within the range of 0 to n-1. The number of flights will be at most 10000.

3. Design an algorithm: To find the cheapest price to reach the destination city within k stops, we can follow these steps:

  1. Create a graph to represent the flights and their prices.
  2. Use Dijkstra's algorithm to find the shortest path from the source city to the destination city while considering the maximum number of stops allowed (k).
    • Initialize a priority queue (min-heap) to store the nodes to be explored.
    • Initialize a dictionary distances to keep track of the minimum distances from the source city to each city visited so far.
    • Add the source city to the priority queue with a distance of 0.
    • While the priority queue is not empty:
      • Pop the node with the smallest distance from the priority queue.
      • If the popped node is the destination city, return the distance to it.
      • If the number of stops made to reach the current node is greater than k, skip it.
      • For each neighbor of the current node:
        • Calculate the total distance to reach the neighbor by adding the edge weight from the current node.
        • If the total distance is less than the distance recorded for the neighbor, update the distance and add the neighbor to the priority queue.
    • If the destination city is not reached within k stops, return -1.

4. Explain your approach: We will create a graph to represent the flights and their prices. Then, we will apply Dijkstra's algorithm to find the shortest path from the source city to the destination city, considering the maximum number of stops allowed. We will use a priority queue (min-heap) to store the nodes to be explored, and a dictionary to track the minimum distances from the source city to each city visited so far. We will iterate until we either reach the destination city or exhaust all possibilities within k stops. If the destination city is not reached within k stops, we will return -1.

5. Write clean and readable code:

python
class Node:
    def __init__(self, city, price):
        self.city = city
        self.price = price


def findCheapestPrice(n, flights, src, dst, k):
    # Create the graph
    graph = [[] for _ in range(n)]
    for flight in flights:
        src_city, dst_city, price = flight
        graph[src_city].append(Node(dst_city, price))

    # Dijkstra's algorithm
    queue = [(0, src, 0)]  # (total_price, current_city, num_stops)
    distances = [float('inf')] * n
    distances[src] = 0

    while queue:
        total_price, city, num_stops = heapq.heappop(queue)
        if city == dst:
            return total_price
        if num_stops > k:
            continue
        if total_price > distances[city]:
            continue

        for neighbor in graph[city]:
            neighbor_city, price = neighbor.city, neighbor.price
            new_price = total_price + price
            if new_price < distances[neighbor_city]:
                distances[neighbor_city] = new_price
                heapq.heappush(queue, (new_price, neighbor_city, num_stops + 1))

    return -1

6. Test your code: Let's test the code with the provided example test case and additional test cases:

python
# Example test case
n = 3
flights = [[0, 1, 100], [1, 2, 100], [0, 2, 500]]
src = 0
dst = 2
k = 1
result = findCheapestPrice(n, flights, src, dst, k)
# Expected output: 200

# Additional test cases
n = 4
flights = [[0, 1, 100], [1, 2, 100], [0, 2, 500], [2, 3, 50]]
src = 0
dst = 3
k = 1
result = findCheapestPrice(n, flights, src, dst, k)
# Expected output: 150

n = 3
flights = [[0, 1, 100], [1, 2, 100], [0, 2, 500]]
src = 0
dst = 2
k = 0
result = findCheapestPrice(n, flights, src, dst, k)
# Expected output: 500

n = 3
flights = [[0, 1, 100], [1, 2, 100], [0, 2, 500]]
src = 0
dst = 1
k = 1
result = findCheapestPrice(n, flights, src, dst, k)
# Expected output: 100

n = 2
flights = [[0, 1, 100]]
src = 0
dst = 1
k = 0
result = findCheapestPrice(n, flights, src, dst, k)
# Expected output: 100

n = 2
flights = [[0, 1, 100]]
src = 0
dst = 1
k = 2
result = findCheapestPrice(n, flights, src, dst, k)
# Expected output: 100

n = 2
flights = [[0, 1, 100]]
src = 0
dst = 1
k = 1
result = findCheapestPrice(n, flights, src, dst, k)
# Expected output: -1

7. Optimize if necessary: The provided solution already uses Dijkstra's algorithm, which has a time complexity of O((V+E)logV), where V is the number of cities and E is the number of flights. Since we are using a min-heap to store the nodes to be explored, the priority queue operations have a time complexity of O(logV). Therefore, the overall time complexity of the solution is efficient.

8. Handle error cases: In the given solution, we assume that the input will be valid and within the specified constraints. We do not handle cases where the number of cities is 0 or negative, the source or destination city is out of range, or the maximum number of stops is negative or zero.

9. Discuss complexity analysis: The time complexity of the provided solution is O((V+E)logV), where V is the number of cities and E is the number of flights. This is because we perform Dijkstra's algorithm, which iterates through each city and its neighboring flights. The logV factor arises from the priority queue operations. The space complexity is O(V), as we need to store the distances from the source city to each city visited so far.

Next Post Previous Post