IndexOutOfBoundsException с приоритетной очередью / ArrayList - PullRequest
Новая
       16

IndexOutOfBoundsException с приоритетной очередью / ArrayList

1 голос
/ 18 мая 2019

Я работаю над этим проектом, чтобы выполнить алгоритм Дейкстры (кажется, для этого много кода, но я должен использовать другие данные классы и ограничения проекта), и я использую очередь с приоритетами, которая помещает соседей текущеговершина в очередь, которая имеет приоритет по кратчайшему расстоянию между вершинами.По большей части он работает нормально, но при добавлении соседних координат в приоритетную очередь (pq), когда он попадает в 7 элементов, он генерирует исключение ArrayOutOfBoundsException в одной из соседних строк.Массив соседей никогда не проходит длину 4 и воссоздается каждый цикл, поэтому я не думаю, что это проблема удаления ArrayList.Я делаю что-то не так с очередью приоритетов или это на самом деле список массивов?Я относительно новичок в использовании обоих из них, так что это моя первая углубленная работа с ними.

Я попытался изменить способ создания очереди приоритетов и ArrayList и их создание / обновление столько, сколькоЯ могу и до сих пор работать, не меняя весь код.Если я закомментирую строку pq.add (nb), то у нее не будет этого исключения, что заставит меня поверить, что именно в этом заключается моя проблема. 


Comparator<Coordinate> compareCoord = new Comparator<Coordinate>(){   
     public int compare(Coordinate a, Coordinate b){    
          if(a.getTerrainCost() > b.getTerrainCost())     return 1;   
          if(a.getTerrainCost() < b.getTerrainCost())     return -1;   
          else                                            return 0;   
         }   
};   
 PriorityQueue<Coordinate> pq = new PriorityQueue<>(compareCoord);   

------------------------------------------------------------------------------
//Loop used to repeat through all the vertices   
while(!unVisited.isEmpty()){   
 //Set current vertex to next in PQ and add/remove from appropriate lists   
    Coordinate smallest = pq.poll();   
....   
List<Coordinate> neighbor = new ArrayList<Coordinate>();   
   if(r!=0)        neighbor.add(map.cells[r-1][c]);   
   if(r!=rows)     neighbor.add(map.cells[r+1][c]); //Line of thrown exception   
   if(c!=0)        neighbor.add(map.cells[r][c-1]);   
   if(c!=columns)  neighbor.add(map.cells[r][c+1]);   

 //Run for loop for each neighbor of vertex   
for(Coordinate nb : neighbor){   
   //Check to make sure the neighbor has not already been visited   
   if(!visited.contains(nb)){   
        //Check path length of the current vertex to the neighbor   
        int index = coords.indexOf(nb);   
        Coordinate n = coords.get(index);   
        int nCost = n.getTerrainCost();   
        int altPath = totalCosts.get(smallest) + nCost;   
        //If path is shorter, update variables and add neighbor to priority  queue   
           if(altPath < totalCosts.get(nb)){   
               totalCosts.put(nb,altPath);   
               prevCoord.put(nb,smallest);   
               pq.add(nb); //If commented out, program runs with no exception   
            }   
    }   
}   
-----------------------------------------------------------------------------
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 7
        at pathFinder.DijkstraPathFinder.<init>(DijkstraPathFinder.java:73)
        at PathFinderTester.main(PathFinderTester.java:294)

Line 73 is commented to find where exception is coming from.

1 Ответ

0 голосов
/ 21 мая 2019

Ошибочная строка содержит map.cells[r+1][c], поэтому проверьте размеры этого массива 2d ячеек, чтобы выяснить, являются ли r+1 и c причиной этого

...