Cheapest Flights Within K Stops medium

Problem Statement

You are given a directed graph with n nodes labeled from 0 to n - 1 where each node represents a city. You are also given edges, where edges[i] = [fromi, toi, pricei] represents a flight from city fromi to city toi with cost pricei.

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: 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 represented by the path: 0 -> 1 -> 2.

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 stops is 500.

Steps

1. Initialization: Create a distance array dist of size n initialized with Infinity, except for dist[src] = 0. Also create an array stops to track the number of stops taken to reach each node. Initialize it with Infinity except stops[src] = 0.

2. Iteration: Iterate k + 1 times (0 to k stops). In each iteration:

   • Create a new distance array newDist to avoid modifying the distances during the current iteration.
   • Iterate through all the edges.
   • For each edge [from, to, price], if dist[from] is not Infinity (meaning we've reached from node) and stops[from] + 1 <= k, we update newDist[to] with the minimum of newDist[to] and dist[from] + price. Also update stops[to] with stops[from] + 1.

3. Update Distances: After each iteration, update dist with newDist.

4. Return Result: After k+1 iterations, return dist[dst] if it's less than Infinity; otherwise return -1.

Explanation

This solution uses Dijkstra's algorithm with a modification to limit the number of stops. The outer loop iterates through the number of stops. The inner loop updates the distances to each node considering the current stop limit. By using a separate newDist array in each iteration we ensure we are always using the shortest distances from the previous iteration. This prevents errors where we might update a node's distance multiple times in the same iteration with longer paths.

Code

function findCheapestPrice(n: number, flights: number[][], src: number, dst: number, k: number): number {
    const dist: number[] = new Array(n).fill(Infinity);
    const stops: number[] = new Array(n).fill(Infinity);
    dist[src] = 0;
    stops[src] = 0;

    for (let i = 0; i <= k; i++) {
        const newDist: number[] = new Array(n).fill(Infinity);
        for (const [from, to, price] of flights) {
            if (dist[from] !== Infinity && stops[from] + 1 <= k) {
                newDist[to] = Math.min(newDist[to], dist[from] + price);
                stops[to] = Math.min(stops[to], stops[from] + 1);
            }
        }
        dist.forEach((d, i) => dist[i] = newDist[i]);

    }

    return dist[dst] === Infinity ? -1 : dist[dst];
};

Complexity

• Time Complexity: O(E * (k + 1)), where E is the number of edges. The nested loops iterate through the edges multiple times.
• Space Complexity: O(N), where N is the number of nodes. The dist and stops arrays take linear space.