运行 Dijkstra 的算法实现时出现 IndexOutOfBoundsException

Question

不是特别确定是什么导致这种IndexOutOfBoundsException情况发生。如果我对所有addFlightPath()参数进行硬编码，代码就可以完美地找到，但是一旦我尝试使用 for 循环来填充flightPathsarrayList，IndexOutOfBoundsException就会抛出一个。我可能遗漏了一些小东西，但我不确定它可能是什么。flightPaths.add(path)在addFlightPath方法内调用时抛出异常public class DijkstrasController{    private FlightDatabase flightDatabase;    private List<Vertex> nodes;    private List<Edge> flightPaths;    public DijkstrasController(FlightDatabase flightDatabase)    {        this.flightDatabase = flightDatabase;        populateDijkstrasGraph(flightDatabase);    }    public String[] runDijkstras(String sourceAirport, String destinationAirport)    {        //Removed for visibility    }    public void populateDijkstrasGraph(FlightDatabase fdb)    {        nodes = new ArrayList<Vertex>();        flightPaths = new ArrayList<Edge>();        for (int i = 0; i < (fdb.getDatabaseSize()); i++)        {            Vertex location = new Vertex("Node_" + i, nodeNumberToNodeLetter(i));            nodes.add(location);         //This block of code throws an IndexOutOfBounds error            AirJourney journey = fdb.getFlightDetails(i);            String pathId = "Path_" + journey.getOriginAirport() + journey.getDestinationAirport();            int sourceAirport = nodeLetterToNodeNumber(journey.getOriginAirport());            int destinationAirport = nodeLetterToNodeNumber(journey.getDestinationAirport());            int distance = journey.getNumberOfMilesToTravel();            addFlightPath(pathId, sourceAirport, destinationAirport, distance);        }

Answer 1

因此，此 IndexOutOfBounds 的原因是由于所讨论的 for 循环阻止了nodesArrayList 正确填充这一事实。

为了解决这个问题，我只是改变了这个代码：

for (int i = 0; i < (fdb.getDatabaseSize()); i++)

        {

            Vertex location = new Vertex("Node_" + i, nodeNumberToNodeLetter(i));

            nodes.add(location);

         //This block of code throws an IndexOutOfBounds error

            AirJourney journey = fdb.getFlightDetails(i);

            String pathId = "Path_" + journey.getOriginAirport() + journey.getDestinationAirport();

            int sourceAirport = nodeLetterToNodeNumber(journey.getOriginAirport());

            int destinationAirport = nodeLetterToNodeNumber(journey.getDestinationAirport());

            int distance = journey.getNumberOfMilesToTravel();

            addFlightPath(pathId, sourceAirport, destinationAirport, distance);

        }

并将第二个块移动到一个单独的 for 循环中，这允许第一个 for 循环在添加飞行路径之前首先填充数组列表。

for (int i = 0; i < (fdb.getDatabaseSize()); i++)

        {

            Vertex location = new Vertex("Node_" + i, nodeNumberToNodeLetter(i));

            nodes.add(location);

        }

        for (int i = 0; i < fdb.getDatabaseSize(); i++)

        {

            AirJourney journey = fdb.getFlightDetails(i);

            String pathId = "Path_" + journey.getOriginAirport() + journey.getDestinationAirport();

            int sourceAirport = nodeLetterToNodeNumber(journey.getOriginAirport());

            int destinationAirport = nodeLetterToNodeNumber(journey.getDestinationAirport());

            int distance = journey.getNumberOfMilesToTravel();

            addFlightPath(pathId, sourceAirport, destinationAirport, distance);

        }

Answer 2

正如评论中提到的，您的异常似乎源于以下行：

Edge path = new Edge(pathId, nodes.get(sourceAirport), nodes.get(destAirport), distance);

让我们回顾一下您的populateDijkstrasGraph()功能（违规部分）：

    for (int i = 0; i < (fdb.getDatabaseSize()); i++)

    {

        Vertex location = new Vertex("Node_" + i, nodeNumberToNodeLetter(i));

        nodes.add(location);

在这里添加由 给出的位置nodeNumberToNodeLetter(i)。

        int sourceAirport = nodeLetterToNodeNumber(journey.getOriginAirport());

        int destinationAirport = nodeLetterToNodeNumber(journey.getDestinationAirport());

在这里，您将获得前两个机场节点的整数值。但是，我们只添加了一个节点！（nodes.add(location)上）。

因此， ifsourceAirport == 0和destinationAirport == 1，nodes当前只包含一个Vertex，nodes.get(sourceAirport)将起作用，而正如预期的那样nodes.get(destinationAirport)会抛出一个IndexOutOfBoundsException。

解决此问题的一种方法是在尝试填充节点之间的边之前填充节点列表。

编辑：如果您还没有，您应该在您的 IDE 中启用行号。它使调试更加容易。此外，您应该熟悉调试和断点 - 这将使您能够很快找到上述错误。

Answer 3

有点猜测工作，但我假设您的代码的工作版本看起来像这样：

public void populateDijkstrasGraph(FlightDatabase fdb)

{

    nodes = new ArrayList<Vertex>();

    flightPaths = new ArrayList<Edge>();

    for (int i = 0; i < (fdb.getDatabaseSize()); i++)

    {

        Vertex location = new Vertex("Node_" + i, nodeNumberToNodeLetter(i));

        nodes.add(location);

     //This block of code throws an IndexOutOfBounds error

     //   AirJourney journey = fdb.getFlightDetails(i);

     //   String pathId = "Path_" + journey.getOriginAirport() + journey.getDestinationAirport();

     //   int sourceAirport = nodeLetterToNodeNumber(journey.getOriginAirport());

     //   int destinationAirport = nodeLetterToNodeNumber(journey.getDestinationAirport());

     //   int distance = journey.getNumberOfMilesToTravel();

     //   addFlightPath(pathId, sourceAirport, destinationAirport, distance);

    }

// Uncommenting this section of code allows the program to function normally

   addFlightPath("Path_AB", 0, 1, 800);

   addFlightPath("Path_BC", 1, 2, 900);

   addFlightPath("Path_CD", 2, 3, 400);

// etc.

这将正常工作，因为您有一个完全填充的nodes列表。但是，如果您addFlightPath进入for-loop，nodes则在循环的第一次迭代中将只包含一个元素。因此，调用nodes.get(1)将失败并出现IndexOutOfBounds异常。

您可能需要循环两次：

for (int i = 0; i < (fdb.getDatabaseSize()); i++)

{

    Vertex location = new Vertex("Node_" + i, nodeNumberToNodeLetter(i));

    nodes.add(location);

}

for (int i = 0; i < (fdb.getDatabaseSize()); i++)

{

    AirJourney journey = fdb.getFlightDetails(i);

    String pathId = "Path_" + journey.getOriginAirport() + journey.getDestinationAirport();

    int sourceAirport = nodeLetterToNodeNumber(journey.getOriginAirport());

    int destinationAirport = nodeLetterToNodeNumber(journey.getDestinationAirport());

    int distance = journey.getNumberOfMilesToTravel();

    addFlightPath(pathId, sourceAirport, destinationAirport, distance);

}