Flight Cost Calculation

Medium Graphs 4 parts 198 lines View on GitHub ↗

Question

Topic: Graphs · Difficulty: Easy → Medium

Flights come as SRC:DST:AIRLINE:COST separated by commas, e.g. "UK:US:FedEx:4,UK:FR:Jet1:2,US:UK:RyanAir:8". Skip malformed entries (fewer than 4 fields, or a cost that isn’t a number). Match places case-insensitively.

Part 1: cheapest direct flight

Return the lowest cost of a direct source → destination flight, or -1.

Part 2: at most one stop

If there’s no direct flight, allow one connection (UK → FR → US) and return the cheapest total.

Part 3: any number of stops, with the route

Return the route, the airlines used and the total cost: UK->FR->DE->US, Jet1->Lufthansa->Delta, 10.

Part 4: cheapest route over any number of stops (not started)

Approach: Part 2 uses a map of src-dst → cheapest cost and tries every middle stop. Part 3 is a DFS with backtracking that records the path and airlines. Part 4 would be Dijkstra.

FlightCostCalculationPart1.java 30 lines GitHub ↗

/**
 * Problem: Flight Cost Calculation
 * Difficulty: Medium
 * Topic: Graphs
 * Question: Cheapest flight from SRC:DST:AIRLINE:COST entries: direct, one stop, then any stops with route and airlines. Full statement in README.md.
 */
package dsa.question5;

public class FlightCostCalculationPart1 {

    public static int flightCostCalculation(String inputString , String source, String destination) {
        String[] flights = inputString.split(",");
        int mincost = Integer.MAX_VALUE;
        source = source.trim(); destination = destination.trim();
        for(int i=0 ;i<flights.length; i++) {
            String[] details = flights[i].split(":");
            if(details.length < 4) {
                continue;
            }
            String s1 = details[0].trim() ; String d1 = details[1].trim() ;
            int cost;
            if(s1.equalsIgnoreCase(source) && d1.equalsIgnoreCase(destination)) {
                try {
                    cost = Integer.valueOf(details[3].trim());
                    mincost = Math.min(mincost, cost);
                } catch (NumberFormatException exception) {

                }
            }

        }
        return mincost == Integer.MAX_VALUE ? -1:mincost;
    }
}

FlightCostCalculationPart2.java 48 lines GitHub ↗

package dsa.question5;

import java.util.HashMap;
import java.util.Map;

public class FlightCostCalculationPart2 {

    public static int flightCostCalculation(String inputString , String source, String destination) {
        HashMap<String , Integer> flightsToCost = new HashMap<>();

        source = source.trim().toLowerCase(); destination = destination.trim().toLowerCase();
        String[] flights = inputString.split(",");
        for(int i=0 ;i<flights.length; i++) {

            String[] details = flights[i].split(":");
            if(details.length < 4) {
                continue;
            }
            String s1 = details[0].trim().toLowerCase() ; String d1 = details[1].trim().toLowerCase() ;
            String key = s1 + "-" + d1;

            int cost;
            try {
                cost = Integer.valueOf(details[3].trim());
                if(flightsToCost.containsKey(key) && flightsToCost.get(key) < cost) {
                    // do nothing
                } else{
                    flightsToCost.put(key, cost);
                }
            } catch (NumberFormatException exception) {
                continue;
            }
        }

        String sourceToDestination = source + "-" + destination;
        if(flightsToCost.containsKey(sourceToDestination)) {
            return flightsToCost.get(sourceToDestination);
        }
        int mincost = Integer.MAX_VALUE;

        for(Map.Entry<String, Integer> entry : flightsToCost.entrySet()) {
            String key = entry.getKey();
            int cost = entry.getValue();

            String[] splitSrcAndDest = key.split("-");
            String s1 = splitSrcAndDest[0] , d1 = splitSrcAndDest[1];
            if(s1.equalsIgnoreCase(source)) {
                // find path from d1 to destination
                String path = d1 + "-" + destination;
                if(flightsToCost.containsKey(path)) {
                    mincost = Math.min(mincost, cost + flightsToCost.get(path));
                }
            }

        }


        return mincost == Integer.MAX_VALUE ? -1 : mincost;
    }
}

FlightCostCalculationPart3.java 85 lines GitHub ↗

package dsa.question5;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

public class FlightCostCalculationPart3 {

    private HashMap<String , List<FlightInfo>> flightsToCost;
    private List<String> isvisited;
    private List<String> path;
    private List<String> flightdetail;
    private int finalCost;

    public class FlightInfo {
        String source;
        String destination;
        int cost;
        String flightname;
        public FlightInfo(String source, String destination, int cost, String flight) {
            this.source = source;
            this.destination = destination;
            this.cost = cost;
            this.flightname = flight;
        }
    }

    private Boolean dfs(String source, String destination, String flightname, int cost) {

        isvisited.add(source);
        path.add(source);
        finalCost += cost;
        if(flightname != null) {
            flightdetail.add(flightname);
        }

        if(source.equalsIgnoreCase(destination)) {
            return true;
        }

        List<FlightInfo> differentFlights = flightsToCost.get(source);

        for(FlightInfo flights : differentFlights) {
            String d1 = flights.destination , n1 = flights.flightname ;
            int cost1 = flights.cost;
            if(!isvisited.contains(d1)) {
                if(dfs(d1, destination, n1, cost1)) {
                    return true;
                }
            }
        }
        isvisited.remove(isvisited.size()-1);
        path.remove(path.size()-1);
        if(!flightdetail.isEmpty()) {
            flightdetail.remove(flightdetail.size()-1);
        }
        finalCost -= cost;

        return false;
    }

    public HashMap<String, Object> flightCostCalculation(String inputString , String source, String destination) {

       flightsToCost = new HashMap<>();
        isvisited = new ArrayList<>();
        path = new ArrayList<>();
        flightdetail = new ArrayList<>();
        finalCost = 0;

        source = source.trim().toLowerCase(); destination = destination.trim().toLowerCase();
        String[] flights = inputString.split(",");

        for(int i=0 ;i<flights.length; i++) {

            String[] details = flights[i].split(":");
            if(details.length < 4) {
                continue;
            }
            String s1 = details[0].trim().toLowerCase() ; String d1 = details[1].trim().toLowerCase(); String name = details[2];

            int cost;
            try {
                cost = Integer.valueOf(details[3].trim());
                flightsToCost.computeIfAbsent(s1, k -> new ArrayList<>()).add(new FlightInfo(s1, d1, cost, name));
            } catch (NumberFormatException exception) {
                continue;
            }
        }

        HashMap<String, Object> result = new HashMap<>();

        if(!dfs(source, destination, null, 0)) {
            result.put("route" , null);
            result.put("method" , null);
            result.put("cost" , 0);
        }else{
            result.put("route" , String.join("->" , path));
            result.put("method" , String.join("->" , flightdetail));
            result.put("cost" , finalCost);
        }

        return result;
    }

}

FlightCostCalculationPart4.java 11 lines GitHub ↗

//package dsa.question5;
//
//import java.util.HashMap;
//
//public class FlightCostCalculationPart4 {
//
//    public HashMap<String, Object> flightCostCalculation(String inputString, String source, String destination) {
//
//
//    }
//}

Demo.java 24 lines GitHub ↗

package dsa.question5;

import java.util.HashMap;

public class Demo {

  public static void main (String[] args) {
      // part1
//      String input = "UK:US:FedEx:4,UK:FR:Jet1:2,US:UK:RyanAir:8,CA:UK:CanadaAir:8";
//      String source = "UK";
//      String destination = "US";
//
//      int cost = FlightCostCalculationPart1.flightCostCalculation(input, source, destination);
//      System.out.println(cost);

//      String input_str = "UK:FR:Jet1:2,FR:US:AmericanAir:6";
//      String source = "UK";
//      String destination = "US";
//      int cost = FlightCostCalculationPart2.flightCostCalculation(input_str, source, destination);
//      System.out.println(cost);

      String input_str = "UK:FR:Jet1:2,FR:DE:Lufthansa:3,DE:US:Delta:5";
      String source = "UK";
      String destination = "US" ;
      FlightCostCalculationPart3 flightCostCalculationPart3 = new FlightCostCalculationPart3();
      HashMap<String, Object> res = flightCostCalculationPart3.flightCostCalculation(input_str, source, destination);
      System.out.println(res);
  }
}