Cheapest Flights Within K Stops - Leetcode Solution

Problem statement:

There are n cities connected by some number of flights. You are given an array flights where flights[i] = [from_i, to_i, price_i] indicates that there is a flight from city from_i to city to_i with cost price_i. You are also given three integers src, dst, and k, return the cheapest price from src to dst with at most k stops. If there is no such route, return -1.

Example 1: Input: flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1 Output: 200 Explanation: The graph is shown. The cheapest price from city 0 to city 2 with at most 1 stop costs 200, as marked red in the picture.

Example 2: Input: flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 0 Output: 500 Explanation: The graph is shown. The cheapest price from city 0 to city 2 with at most 0 stop costs 500, as marked blue in the picture.

Approach:

The problem statement can be solved using Dijkstra's algorithm with a slight modification to check for the maximum number of stops. Initially, we create a graph using the flights array where the edges are represented by the prices. We also create a visited array to keep track of the visited nodes. We start with the source node and keep updating the distances of the neighboring nodes. However, we only visit the neighbor nodes if the number of stops is less than or equal to k. Additionally, we keep track of the number of stops using another array. Once we reach the destination node or have visited all the nodes, we return the minimum distance.

Algorithm:

1. Create a graph using the flights array where the edges are represented by the prices.
2. Initialize the minimum distances for all nodes as infinity.
3. Initialize the distances for the source node as 0 and add it to a priority queue.
4. Initialize the number of stops for the source node as 0.
5. While the priority queue is not empty, do the following: a. Get the node with the minimum distance from the priority queue. b. If the node is the destination node, return the minimum distance. c. If the number of stops is greater than k, continue to the next node. d. Mark the node as visited. e. Update the distances of the neighboring nodes. f. If the neighboring node is not visited and the distance through the current node is less than the current distance of the neighboring node, update the distance of the neighboring node and add it to the priority queue. g. Increment the number of stops for the neighboring node.
6. If the destination node is not found, return -1.

Code:

Here is the Python code for the Cheapest Flights Within K Stops problem:

import heapq

def findCheapestPrice(n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int: # Create a graph where the edges are represented by the prices graph = {} for u, v, w in flights: if u not in graph: graph[u] = [] graph[u].append((v, w))

# Initialize the minimum distances for all nodes as infinity
dist = [float('inf')] * n

# Initialize the distances for the source node as 0
dist[src] = 0

# Add the source node to a priority queue
pq = [(0, src, -1)]

# While the priority queue is not empty, do the following
while pq:
    # Get the node with the minimum distance from the priority queue
    d, u, s = heapq.heappop(pq)

    # If the node is the destination node, return the minimum distance
    if u == dst:
        return d

    # If the number of stops is greater than k, continue to the next node
    if s >= k:
        continue

    # Mark the node as visited
    visited[u] = True

    # Update the distances of the neighboring nodes
    for v, w in graph.get(u, []):
        # If the neighboring node is not visited and the distance through the current node is less than the current distance of the neighboring node, update the distance of the neighboring node and add it to the priority queue
        if not visited[v] and d + w < dist[v]:
            dist[v] = d + w
            heapq.heappush(pq, (dist[v], v, s+1))

# If the destination node is not found, return -1
return -1

Time complexity:

The time complexity of the algorithm is O(E log V), where E is the number of edges and V is the number of vertices in the graph. This is because we are using a priority queue to store the nodes with the minimum distance, which takes O(log V) time to insert and remove nodes.

Space complexity:

The space complexity of the algorithm is O(V + E), where V is the number of vertices and E is the number of edges in the graph. This is because we are using visited array, dist array, and priority queue.

1