Cheapest Flights Within K Stops medium

Problem Statement

You are given a directed graph with n nodes labeled from 0 to n - 1 represented by a graph array flights, where flights[i] = [fromi, toi, pricei] indicates the cost of a flight from node fromi to node toi with cost pricei.

You are also given three integers src, dst, and k. 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, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1

Output: 200

Explanation: The graph looks like this:

0 --100--> 1 --100--> 2
0 --500--> 2

The cheapest price from node 0 to node 2 with at most 1 stop costs 200 (0 -> 1 -> 2).

Example 2

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

Output: 500

Explanation: The cheapest price from node 0 to node 2 with at most 0 stop costs 500 (0 -> 2).

Steps

1. Initialization: Create a distance array dist of size n initialized with Int32.MaxValue. Set dist[src] = 0. Also create a priority queue pq to store nodes and their distances. Add (0, src) to pq.

2. Iteration: While pq is not empty:

   • Poll the node curr and its distance currDist from pq.
   • If currDist is greater than the current distance to curr in dist, continue (this avoids revisiting nodes with higher cost).
   • Iterate through the flights array. If a flight starts at curr, calculate the new distance to the destination node.
   • If the new distance is less than the current distance to the destination node in dist, update dist and add the destination node and its new distance to pq.
   • Keep track of the number of stops (stops) for each path. If stops exceeds k, stop processing the current path.

3. Result: After iterating through all possible paths, dist[dst] will hold the cheapest price from src to dst with at most k stops. If dist[dst] is still Int32.MaxValue, it means no path exists, so return -1.

Explanation

This solution uses Dijkstra's algorithm with a modification to handle the constraint of at most k stops. The priority queue ensures that we always explore the shortest paths first. By keeping track of stops, we prevent paths with more than k stops from being considered, which ensures we find the cheapest path within the given constraints.

Code

using System;
using System.Collections.Generic;

public class Solution {
    public int FindCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
        // Initialize distances to infinity
        int[] dist = new int[n];
        Array.Fill(dist, int.MaxValue);
        dist[src] = 0;

        // Priority queue to store (distance, node) pairs
        PriorityQueue<(int dist, int node), int> pq = new PriorityQueue<(int, int), int>();
        pq.Enqueue((0, src), 0);

        for (int stops = 0; stops <= k; stops++) {
            int count = pq.Count;
            for (int i = 0; i < count; i++) {
                (int d, int curr) = pq.Dequeue();
                if (d > dist[curr]) continue;

                foreach (int[] flight in flights) {
                    if (flight[0] == curr) {
                        int next = flight[1];
                        int price = flight[2];
                        if (dist[next] > d + price) {
                            dist[next] = d + price;
                            pq.Enqueue((dist[next], next), dist[next]);
                        }
                    }
                }
            }
        }

        return dist[dst] == int.MaxValue ? -1 : dist[dst];
    }
}

Complexity

• Time Complexity: O(E log V), where E is the number of edges (flights) and V is the number of vertices (nodes). This is due to the use of the priority queue.
• Space Complexity: O(V), primarily for the dist array and the priority queue. In the worst case the priority queue could hold all the vertices.