Я работаю над этим проектом, чтобы выполнить алгоритм Дейкстры (кажется, для этого много кода, но я должен использовать другие данные классы и ограничения проекта), и я использую очередь с приоритетами, которая помещает соседей текущеговершина в очередь, которая имеет приоритет по кратчайшему расстоянию между вершинами.По большей части он работает нормально, но при добавлении соседних координат в приоритетную очередь (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.