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.