java - 运行 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);
        }

// 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)

标签： javaindexoutofboundsexception

Answer 1

So, the reason for this IndexOutOfBounds was being caused by the fact that the for loop in question prevented the nodes ArrayList from being populated properly.

To fix this, I simply changed this code:

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

And moved the second block into a separate for loop, this allows the first for loop to populate the arraylist first, before the flight paths are added.

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