Cheapest Flights Within K Stops

class Solution {
public:
    int findLowestCost(int cities, vector<vector<int>>& routes, int start, int end, int maxStops) {
        vector<vector<pair<int, int>>> graph(cities);
        for (const auto& r : routes) {
            graph[r[0]].emplace_back(r[1], r[2]);
        }
        vector<int> minStops(cities, numeric_limits<int>::max());
        priority_queue<vector<int>, vector<vector<int>>, greater<vector<int>>> minHeap;
        minHeap.push({0, start, 0});

        while (!minHeap.empty()) {
            auto current = minHeap.top();
            minHeap.pop();
            int cost = current[0];
            int city = current[1];
            int stops = current[2];
            
            if (stops > minStops[city] || stops > maxStops + 1) continue;
            minStops[city] = stops;

            if (city == end) return cost;

            for (const auto& [nextCity, travelCost] : graph[city]) {
                minHeap.push({cost + travelCost, nextCity, stops + 1});
            }
        }
        return -1;
    }
};

The following solution in C++ helps find the cheapest flight price within a specified number of stops (K stops) between routes in a flight network.

• Begin by constructing a graph where each city is a node, and direct flights between them represent the edges with weights corresponding to the flight costs.
• Implement an approach inspired by the Breadth-First Search (BFS), but instead of a queue, use a min-heap (or priority queue) to always expand the least costly flight path first.
• Maintain a vector minStops that records the minimum number of stops needed to reach each city. Initialize this vector with the maximum possible value for comparison during the search.
• Utilize the min-heap to assess routes dynamically based on cumulative cost, proceeding with the current city and number of stops taken to reach there.
• For each city processed, if its number of stops exceeds either the previous minimum stops recorded for that city or the allowed maximum plus one, skip further processing for efficiency.
• If the destination city is reached, return the total cost calculated for that path.
• If no paths fulfill the conditions (reaching the destination within the allowed number of stops) by the time the priority queue is exhausted, return -1 to indicate that no valid path was found.

This method efficiently navigates potentially large networks by leveraging both cost and number of stops as key criteria, ensuring the search remains focused and optimal. Adjustments to this algorithm may include changing the priority queue mechanics or the condition checks based on specific needs related to the network scale or constraints.

class Solution {
    public int minCostFlight(int totalNodes, int[][] edges, int start, int end, int maxStops) {
        Map<Integer, List<int[]>> graph = new HashMap<>();
        for (int[] flight : edges)
            graph.computeIfAbsent(flight[0], x -> new ArrayList<>()).add(new int[] { flight[1], flight[2] });

        int[] stops = new int[totalNodes];
        Arrays.fill(stops, Integer.MAX_VALUE);
        PriorityQueue<int[]> queue = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        queue.offer(new int[] { 0, start, 0 });

        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int cost = current[0];
            int node = current[1];
            int doneStops = current[2];
            if (doneStops > stops[node] || doneStops > maxStops + 1)
                continue;
            stops[node] = doneStops;
            if (node == end)
                return cost;
            if (!graph.containsKey(node))
                continue;
            for (int[] next : graph.get(node)) {
                queue.offer(new int[] { cost + next[1], next[0], doneStops + 1 });
            }
        }
        return -1;
    }
}

The solution presented here addresses the problem of finding the cheapest flight route with constraints on the number of stops using Java. Specifically, it solves for the minimum cost of flying from a starting node to a destination node within a limited number of allowable stops.

Here's an overview of the implementation method:

• First, a graph is constructed where each node represents a city, and the edges represent the flight routes between the cities with associated costs. This graph is built using a HashMap to map each node to a list of its destination nodes with corresponding flight costs.

• Initial conditions are set up using a priority queue to facilitate the retrieval of the current lowest-cost path during algorithm execution. The algorithm employs Dijkstra’s shortest path approach with modifications to account for the stop constraint.

• A PriorityQueue is used where each element is an array consisting of the current cost to reach the node, the node itself, and the number of stops made to reach that node. The priority queue is prioritized by the flight costs to efficiently fetch the least expensive route first.

• For each node processed, the algorithm checks whether the traveled path exceeds either the minimal number of stops previously recorded to reach the node or the maximum allowed stops. If it does not, the route is considered further by exploring all connecting flights and accumulating costs and stops.

• The algorithm halts when the destination node is reached with the smallest cost within the acceptable stop limit, returning this minimum cost. If the destination is unreachable under the specified conditions, the algorithm returns -1.

This strategic use of graph representation, along with a priority queue, ensures the solution is both time-efficient and straightforward, leveraging stops and cost considerations effectively to determine the optimal route.