Cheapest Flight within K Stops

XXX. Cheapest Flights Within K Stops

Graph

Dijkstra's

Priority Queue

Problem Statement:

Find the cheapest price from source to destination city with at most K stops. Flight routes are provided as [source, destination, price].

• Maximum K stops allowed
• Prices are non-negative
• Return -1 if no such route exists

Implementation:

// Helper classes for storing city and cost information
class Pair {
    int city, cost;
    Pair(int city, int cost) {
        this.city = city;
        this.cost = cost;
    }
}

class City {
    int city, distFromSrc, costFromSrc;
    City(int city, int distFromSrc, int cost) {
        this.city = city;
        this.distFromSrc = distFromSrc;
        this.costFromSrc = cost;
    }
}

class Solution {
    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {
        if(n <= 0 || flights == null || flights.length == 0 || K < 0) 
            return -1;

        // Build adjacency list representation
        List> graph = new ArrayList<>();
        buildGraph(graph, n, flights);

        // Priority queue ordered by cost
        Queue pQueue = new PriorityQueue<>(
            (City c1, City c2) -> c1.costFromSrc - c2.costFromSrc
        );
        pQueue.offer(new City(src, 0, 0));

        // Process cities in order of increasing cost
        while (!pQueue.isEmpty()) {
            City curr = pQueue.poll();

            if (curr.city == dst)              // Found destination
                return curr.costFromSrc;

            if (curr.distFromSrc > K)          // Exceeded stops limit
                continue;

            // Add all neighbors to queue
            List neighbors = graph.get(curr.city);
            for (Pair neighbor: neighbors) 
                pQueue.offer(new City(
                    neighbor.city, 
                    curr.distFromSrc + 1,      // Increment stops
                    curr.costFromSrc + neighbor.cost  // Add flight cost
                ));
        }
        return -1;                             // No valid path found
    }

    private void buildGraph(List> graph, int n, int[][] flights) {
        for (int i = 0; i < n; i++)
            graph.add(new ArrayList<>());
        
        for (int[] flight: flights)
            graph.get(flight[0]).add(new Pair(flight[1], flight[2]));
    }
}

Complexity:

Time Complexity: O(V * E * log(V * E)) where V is number of cities, E is number of flights
Space Complexity: O(V + E) for graph and queue

Key Points:

• **Modified Dijkstra's Algorithm**:
  • Uses stops count as additional constraint
  • Priority queue ordered by total cost
  • Early termination when destination found
• **Graph Representation**:
  • Adjacency list using ArrayList
  • Store both destination and cost in Pair
  • Direction matters (one-way flights)
• **State Tracking**:
  • Track stops count for each path
  • Track accumulated cost
  • Skip paths exceeding K stops

Implementation Notes:

• **Optimization Features**:
  • Early return when destination found
  • Skip processing paths with too many stops
  • Priority queue ensures cheapest paths processed first
• **Edge Cases**:
  • Check for invalid input conditions
  • Handle case when no path exists
  • Consider zero stops allowed