运行Dijkstra算法实现时的java IndexOutOfBoundsException

Question

不太清楚是什么导致了这种IndexOutOfBoundsException的发生。如果我硬编码所有的addFlightPath()参数，那么代码会非常有效，但是一旦我尝试使用for循环填充flightPathsarrayList，就会抛出一个IndexOutOfBoundsException。我可能错过了一些小东西，但我不确定可能是什么

在addFlightPath方法中调用flightPaths.add(path)时引发异常

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

// 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);
//      addFlightPath("Path_BF", 1, 5, 400);
//      addFlightPath("Path_DE", 3, 4, 300);
//      addFlightPath("Path_EB", 4, 1, 600);
//      addFlightPath("Path_CE", 2, 4, 200);
//      addFlightPath("Path_DC", 3, 2, 700);
//      addFlightPath("Path_EB", 4, 1, 500);
//      addFlightPath("Path_FD", 5, 3, 200);
//      addFlightPath("Path_DE", 3, 4, 400);
//      addFlightPath("Path_CE", 2, 4, 300);

    }

    private void addFlightPath(String pathId, int sourceAirport, int destAirport, int distance)
    {
        Edge path = new Edge(pathId, nodes.get(sourceAirport), nodes.get(destAirport), distance);
        flightPaths.add(path); //IndexOutOfBounds exception is thrown here
    }

}

堆栈跟踪

Exception in thread "main" java.lang.IndexOutOfBoundsException: Index: 1, Size: 1
    at java.util.ArrayList.rangeCheck(ArrayList.java:657)
    at java.util.ArrayList.get(ArrayList.java:433)
    at core.dijkstras2.DijkstrasController.addFlightPath(DijkstrasController.java:83)
    at core.dijkstras2.DijkstrasController.populateDijkstrasGraph(DijkstrasController.java:63)
    at core.dijkstras2.DijkstrasController.<init>(DijkstrasController.java:19)
    at core.dijkstras2.DDriver.main(DDriver.java:10)

Answer 1

如评论中所述，您的例外情况似乎源于以下几行：

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)以上）

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

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

编辑：如果还没有，应该在IDE中启用行号。它使调试变得更容易。此外，您应该熟悉调试和断点——这会让您很快找到上述错误

Answer 2

有点猜测，但我假设您的代码工作版本如下所示：

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-循环中，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);
}

Answer 3

因此，这个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循环在添加飞行路径之前首先填充arraylist

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 4

当你做循环时，总是从你使用的列表的0到大小-1开始。如果列表中有5个位置，则循环从0变为4。也许是你的问题

试着说：

for (int i = 0; i < (fdb.getDatabaseSize()-1); i++)
{}