Cheapest Flights Within K Stops medium

Problem Statement

You are given a graph represented by an array of edges where edges[i] = [from_node, to_node, weight] represents a directed edge from from_node to to_node with weight weight. You are also given the integer n, the number of nodes in the graph (labeled from 0 to n - 1), the source node src, the destination node dst, and the integer k, the maximum number of stops.

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 node 0 to node 2 with at most 1 stop costs 200, as depicted in the example image. Note that you can also take the path 0 -> 2 which costs 500 but this is not the cheapest.

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 node 0 to node 2 with at most 0 stop costs 500 because there is a direct edge from 0 to 2.

Steps

1. Initialization: Create a distance array dist of size n initialized with infinity (except for the source node, which is 0). Also, create a pq (priority queue) to store nodes and their distances, ordered by distance. Add the source node to the pq.

2. Iteration: While the pq is not empty, perform the following:

   • Dequeue the node u with the smallest distance from the pq.
   • If u is the destination node, return its distance.
   • For each edge from u to v with weight w:
     • If the current distance to v is greater than the distance to u plus w, and the number of stops stops is less than or equal to k:
       • Update the distance to v to dist[u] + w.
       • Add v to the pq with the updated distance and stops.

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

Explanation

This solution uses Dijkstra's algorithm with a modification to track the number of stops. The priority queue ensures that we always explore the node with the shortest distance first. The stops variable keeps track of the number of stops taken to reach a node, preventing paths with more than k stops from being considered. This ensures we find the cheapest path within the constraint of k stops.

Code

import java.util.PriorityQueue;
import java.util.Arrays;

class Solution {
    public int findCheapestPrice(int n, int[][] edges, int src, int dst, int k) {
        // Adjacency list representation of the graph
        List<int[]>[] graph = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new ArrayList<>();
        }
        for (int[] edge : edges) {
            graph[edge[0]].add(new int[]{edge[1], edge[2]});
        }

        // Dijkstra's algorithm with stop count
        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[src] = 0;

        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        pq.offer(new int[]{0, src, 0}); // {distance, node, stops}

        while (!pq.isEmpty()) {
            int[] curr = pq.poll();
            int d = curr[0];
            int u = curr[1];
            int stops = curr[2];

            if (u == dst) return d;
            if (stops > k) continue;

            for (int[] edge : graph[u]) {
                int v = edge[0];
                int w = edge[1];
                if (dist[v] > d + w) {
                    dist[v] = d + w;
                    pq.offer(new int[]{dist[v], v, stops + 1});
                }
            }
        }

        return -1;
    }
}

Complexity

• Time Complexity: O(E log V), where E is the number of edges and V is the number of vertices. This is due to the priority queue operations in Dijkstra's algorithm.

• Space Complexity: O(V + E), primarily for the adjacency list and the distance array. The priority queue's size is bounded by the number of edges in the worst case.