javagraphjgrapht

JGraphT graph shortest path


I am trying to calculate the total cost of the shortest path for a flight itinerary system, but it seems to be calculate the number of paths it take instead of the length/cost. I am unable to workout how to get the cost for each journey from the Flight_Info object.

Here is my code:

import java.util.Scanner;
import org.jgrapht.graph.*;
import org.jgrapht.Graphs;
import org.jgrapht.alg.DijkstraShortestPath;

public class Flights2 {

public static SimpleDirectedWeightedGraph<String, Flight_Info> createGraph() {

    SimpleDirectedWeightedGraph<String, Flight_Info> airport = new SimpleDirectedWeightedGraph<String, Flight_Info>(
            Flight_Info.class);

    String Edinburgh = new String("Edinburgh");
    String Heathrow = new String("Heathrow");
    String Dubai = new String("Dubai");
    String Sydney = new String("Sydney");
    String KualaLumpur = new String("Kuala Lumpur");
    String Frankfurt = new String("Frankfurt");
    String Aukland = new String("Aukland");
    String RioDeJanerio = new String("Rio De Janerio");
    String NewYork = new String("New York");
    String Santiago = new String("Santiago");

    airport.addVertex(Edinburgh);
    airport.addVertex(Heathrow);
    airport.addVertex(Dubai);
    airport.addVertex(Sydney);
    airport.addVertex(KualaLumpur);
    airport.addVertex(Frankfurt);
    airport.addVertex(Aukland);
    airport.addVertex(RioDeJanerio);
    airport.addVertex(NewYork);
    airport.addVertex(Santiago);



    Flight_Info FL1001 = new Flight_Info("FL1001", 1530, 1630, 1, 80);
    airport.addEdge(Edinburgh, Heathrow, FL1001);
    Flight_Info FL1002 = new Flight_Info("FL1002", 1630, 1730, 1, 80);
    airport.addEdge(Heathrow, Edinburgh, FL1002);
    Flight_Info FL1003 = new Flight_Info("FL1003", 1630, 1730, 1, 80);
    airport.addEdge(Heathrow, Dubai, FL1003);
    Flight_Info FL1004 = new Flight_Info("FL1004", 1630, 1730, 1, 80);
    airport.addEdge(Dubai, Heathrow, FL1004);
    Flight_Info FL1005 = new Flight_Info("FL1005", 1630, 1730, 1, 80);
    airport.addEdge(Heathrow, Sydney, FL1005);
    Flight_Info FL1006 = new Flight_Info("FL1006", 1630, 1730, 1, 80);
    airport.addEdge(Sydney, Heathrow, FL1006);
    Flight_Info FL1007 = new Flight_Info("FL1007", 1630, 1730, 1, 80);
    airport.addEdge(Dubai, KualaLumpur, FL1007);
    Flight_Info FL1008 = new Flight_Info("FL1008", 1630, 1730, 1, 80);
    airport.addEdge(KualaLumpur, Dubai, FL1008);
    Flight_Info FL1009 = new Flight_Info("FL1009", 1630, 1730, 1, 80);
    airport.addEdge(Dubai, Edinburgh, FL1009);
    Flight_Info FL1010 = new Flight_Info("FL10010", 1630, 1730, 1, 80);
    airport.addEdge(Edinburgh, Dubai, FL1010);
    Flight_Info FL1011 = new Flight_Info("FL1011", 1630, 1730, 1, 80);
    airport.addEdge(KualaLumpur, Sydney, FL1011);
    Flight_Info FL1012 = new Flight_Info("FL1012", 1630, 1730, 1, 80);
    airport.addEdge(Sydney, KualaLumpur, FL1012);
    Flight_Info FL1013 = new Flight_Info("FL1013", 1630, 1730, 1, 80);
    airport.addEdge(Edinburgh, Frankfurt, FL1013);
    Flight_Info FL1014 = new Flight_Info("FL1014", 1630, 1730, 1, 80);
    airport.addEdge(Frankfurt, Edinburgh, FL1014);
    Flight_Info FL1015 = new Flight_Info("FL1015", 1630, 1730, 1, 80);
    airport.addEdge(Sydney, Aukland, FL1015);
    Flight_Info FL1016 = new Flight_Info("FL1016", 1630, 1730, 1, 80);
    airport.addEdge(Aukland, Sydney, FL1016);
    Flight_Info FL1017 = new Flight_Info("FL1017", 1630, 1730, 1, 80);
    airport.addEdge(RioDeJanerio, NewYork, FL1017);
    Flight_Info FL1018 = new Flight_Info("FL1018", 1630, 1730, 1, 80);
    airport.addEdge(NewYork, RioDeJanerio, FL1018);
    Flight_Info FL1019 = new Flight_Info("FL1019", 1630, 1730, 1, 80);
    airport.addEdge(Santiago, NewYork, FL1019);
    Flight_Info FL1020 = new Flight_Info("FL1020", 1630, 1730, 1, 80);
    airport.addEdge(NewYork, Santiago, FL1020);

    return airport;
}

public static void itinerary(SimpleDirectedWeightedGraph<String, Flight_Info> airport, String departure,
        String destination) {
    DijkstraShortestPath<String, Flight_Info> p = new DijkstraShortestPath<String, Flight_Info>(airport, departure,
            destination);




    System.out.println(p.getPathEdgeList());
    System.out.println("Cost of shortest (i.e cheapest) path = £" + p.getPathLength() );
}

public static void main(String args[]) {

    SimpleDirectedWeightedGraph<String, Flight_Info> airport = createGraph();
    System.out.println("The following airports are in use:" + airport.vertexSet());
    @SuppressWarnings("resource")
    Scanner s = new Scanner(System.in);
    System.out.println("Please enter the starting airport:");
    String departure = s.nextLine();
    System.out.println("Please enter the destination aiport:");
    String destination = s.nextLine();
    itinerary(airport, departure, destination);


}

  import org.jgrapht.graph.DefaultWeightedEdge;

public class Flight_Info extends DefaultWeightedEdge {

private String departure, destination, flightNumber;
private int departureTime, arrivalTime, duration, ticketPrice;

public Flight_Info() {

}

public Flight_Info(String flightNumber, int departureTime, int arrivalTime, int duration, int ticketPrice) {
    super();
    this.flightNumber = flightNumber;
    this.departureTime = departureTime;
    this.arrivalTime = arrivalTime;
    this.duration = duration;
    this.ticketPrice = ticketPrice;

}


public int getDuration(){
    return duration;
}

Solution

  • I'm only guessing, but it seems that your Flight_Info class lacks a getter for the ticket price. Then you're reading the cost of the computed shortest path in edges. I think it would be better to iterate over the edges of the shortest path and sum up the ticket prices.

    As I said: Just guessing after a short look... =)

    Best regards

    Alex