Алгоритм кратчайшего пути Dijkstra, не возвращающий самый короткий путь с наименьшим весом

Question

Я использую библиотеку графов, названную JGraphT, и в моей программе у меня несколько вершин, соединенных вместе краем с весом стоимости путешествия.

В одном примере, где я весит всего лишь целым числом, он работает! Но когда я изменяю это на использование моего класса FlightData в качестве веса, он не работает.

Вот мой код с весом, как только целое число:

List<DefaultWeightedEdge> path = DijkstraShortestPath.findPathBetween(graph, start, end); 
    for(int i = 0; i < path.size(); i++) { 
     DefaultWeightedEdge edge = path.get(i); 
     System.out.println((i+1) + " " + graph.getEdgeSource(edge) + " -> " + graph.getEdgeTarget(edge)); 
    } 

Вот мой код для веса, как мой FlightData класс:

List<FlightData> path = DijkstraShortestPath.findPathBetween(graph, start, end);  
for(int i = 0; i < path.size(); i++) { 
     FlightData f = path.get(i); 
    System.out.println((i+1) + " " + graph.getEdgeSource(f) + " -> " + graph.getEdgeTarget(f)); 
} 

Мой класс FlightData это просто просто класс с использованием методов доступа:

import org.jgrapht.graph.DefaultWeightedEdge; 

public class FlightData extends DefaultWeightedEdge 
{ 
    private String flightNumber, depTime, arrTime; 
    private double price; 

    public FlightData(String flightNumber, String depTime, 
      String arrTime, double price) { 
     this.flightNumber = flightNumber; 
     this.depTime = depTime; 
     this.arrTime = arrTime; 
     this.price = price; 
    } 

    public String getFlightNumber() { 
     return flightNumber; 
    } 
    public String getDepartureTime() { 
     return depTime; 
    } 
    public String getArrivalTime() { 
     return arrTime; 
    } 
    public double getFlightPrice() { 
     return price; 
    } 
} 

Может ли кто-нибудь указать мне в правильном направлении, почему один оборот самый короткий путь с самым низким весом, а другой с кратчайшим путем и не обязательно самым низким весом? (Если есть прямой путь между двумя вершинами, он просто вернет это!)

Answer 1

Вам необходимо переопределить DefaultWeightedEdge.getWeight() в FlightData, например. вернуться price:

@Override 
protected double getWeight() { 
    return price; 
} 

В противном случае, вы будете использовать вес краевого по умолчанию, который 1.0.