Cheapest flight with K stops

Cheapest flight with K stops

You are given an array flights where flights[i] = [fromi, toi, pricei] indicates that there is 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.

This problem can be solved in multiple ways the, one of the the way is to use BFS with calculation route cost and noOfStops at each level(neighbour)

Note: Dijkastra only path with positive weight and keep the cost minimum

We create adjacency list of time it takes to visit each vertices and then place checks in the code to find at each level whats the minimum cost to travel that vertice

      public int findCheapestPrice(int n, int[][] flights, int source, int dest, int noOfStops) {
        
        Map<Integer, List<Pair>> adjacencyList = new HashMap<>();
        int cheapFlightCost [] = new int[flights.length + 1];
        for (int i =0; i < flights.length; i++) {
            List<Pair> list = new ArrayList<>();
            adjacencyList.put(flights[i][0], list);
        }

        for (int i=0; i<flights.length; i++) {
            List<Pair> flightPair = adjacencyList.get(flights[i][0]);
            flightPair.add(new Pair(flights[i][1], flights[i][2]));
            adjacencyList.put(flights[i][0], flightPair);
        }

        for (int i=0; i<n; i++) {
            cheapFlightCost[i] = Integer.MAX_VALUE;
        }
        //There is no need to prefill the array because we need to give a number based on K
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{source, 0, 0});
        cheapFlightCost[source] = 0;

        //int stopsDone = 0;
        while (!queue.isEmpty()) {
            int currentCity[] = queue.poll();
            //System.out.println("CurrentCity : "+ currentCity[0] + " stops completed " + currentCity[2]);
           
            int stopsCompleted = currentCity[2];
            if(currentCity[0] == dest && stopsCompleted == noOfStops+1) {
               return currentCity[1];
            }
            if(!adjacencyList.containsKey(currentCity[0])) {
                continue;  //important failing for nullpointer
            }
            //cost calculation
            for (Pair neighbour : adjacencyList.get(currentCity[0])) { 
                int arrivalTimeCost = currentCity[1] + neighbour.val;
               if(cheapFlightCost[neighbour.node] > arrivalTimeCost) {
                  cheapFlightCost[neighbour.node] = arrivalTimeCost; //new cost based on the last connected flight
                  int stopsDone = currentCity[2];  //should be based on parent otherwise when there are multiple nodes in a level, the stop cal becomes wrong
                  queue.add(new int[]{neighbour.node, arrivalTimeCost, stopsDone+1});   //This way if the cost is coming a min we would update the node value
               }
            }
        }
        return -1;  
    }
}

public class Pair {

    public Integer node;
    public Integer val;

    public Pair(int n, int v) {
        this.node = n;
        this.val = v;
    }