L'algorithme de plus court chemin de Dijkstra ne retourne pas le chemin le plus court avec le plus petit poids

Question

J'utilise une bibliothèque de graphes appelée JGraphT et dans mon programme j'ai plusieurs vertex reliés par un bord avec un poids du coût du voyage.

Dans un exemple où je pèse juste un nombre entier, cela fonctionne! Mais quand je change cela en utilisant ma classe FlightData comme poids, ça ne marche pas.

Voici mon code avec le poids comme un simple entier:

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)); 
    } 

Voici mon code pour le poids que ma classe 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)); 
} 

Ma classe FlightData est tout simplement une classe avec des méthodes d'accesseur:

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; 
    } 
} 

Quelqu'un peut-il m'indiquer dans la bonne direction pourquoi un rev eals le chemin le plus court avec le poids le plus bas et l'autre avec le chemin le plus court et pas nécessairement le poids le plus bas? (S'il y a un chemin direct entre deux vertex, il retournera juste cela!)

Answer 1

Vous devez remplacer DefaultWeightedEdge.getWeight() dans FlightData, par ex. pour revenir price:

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

Sinon, vous utiliserez le poids de bord par défaut, ce qui est 1.0.