多线程Java：带有ThreadPool和CountDownLatch的Dijkstra算法导致越界异常

Question

这是基于我之前的问题：Wait in a loop until tasks of ThreadPoolExecutor are done before continuing

我想让Dijkstra算法并行。 我实现了一个倒计时锁，等待所有任务完成。每个任务都会查看一组特定的边，这些边连接到迭代中的当前节点。所以8条边和2条线程意味着每个任务将看4条边。完成所有任务后，我们将继续下一个节点

由于某些原因，索引的起点和终点（连接边的数量）有时会高于可用边。我在倒计时之前就遇到了这个问题，我想这是因为任务没有等我们继续之前完成

为了查看一些调试行，我放了一个线程。Sleep（100）in查看输出时，我注意到当我放慢速度时，数组不会超出界限

最后，我注意到循环卡在节点0（源节点）上。这应该是不可能的，因为我们从这个节点开始，并设置为true。我不知道这是因为代码中的其他错误还是另一个bug

此函数只调用一次，并将在图中的所有节点之间循环：

public void apply(int numberOfThreads) {
        ThreadPoolExecutor executor = (ThreadPoolExecutor) Executors.newFixedThreadPool(numberOfThreads + 1);
        CountDownLatch cdl = new CountDownLatch(numberOfThreads);

        class DijkstraTask implements Runnable {

            private int start;
            private int end;
            private final CountDownLatch cdl;

            public DijkstraTask(int start, int end, CountDownLatch cdl) {
                this.start = start;
                this.end = end;
                this.cdl = cdl;
            }

            @Override
            public void run() {
                calculateShortestDistances(start, end, cdl);
            }
        }

        currentNode = 0;
        this.nodes[0].setDistanceFromSource(0);

        // Visit every node, in order of stored distance
        for (int i = 0; i < this.nodes.length; i++) {
            // Loop round the edges that are joined to the current node
            currentNodeEdges = this.nodes[currentNode].getEdges();

            int edgesPerThread = currentNodeEdges.size() / numberOfThreads;
            int modulo = currentNodeEdges.size() % numberOfThreads;

            System.out.println(i);

            //Add task for each node
            for (int t = 0; t < numberOfThreads; t++) {
                int start = edgesPerThread * t;
                int end = edgesPerThread * (t + 1);

                executor.execute(new DijkstraTask(start, end, cdl));
                System.out.println("Start: " + start + ". End: " + end + ". Total: " + currentNodeEdges.size());

               //If we have a modulo we will add another task to look at the remaining edges
                if (modulo > 0 && numberOfThreads == (t + 1)) {
                    start = edgesPerThread * (t + 1);
                    end = edgesPerThread * (t + 1) + modulo;

                    executor.execute(new DijkstraTask(start, end, cdl));
                    System.out.println("Modulo start: " + start + ". End: " + end + ". Total: " + currentNodeEdges.size());
                }
            }
            //wait for all threads to finish
            try {
                cdl.await();
                System.out.println("-all done-");
            } catch (InterruptedException ex) {
                ex.printStackTrace();
            }

            // All neighbours are checked so this node is now visited
            nodes[currentNode].setVisited(true);

            //Look through the results of the tasks and get the next node that is closest by
            currentNode = getNodeShortestDistanced();
        }

        executor.shutdown();
    }

任务调用以下函数，将连接的EGE从开始索引处理到结束索引：

public void calculateShortestDistances(int start, int end, CountDownLatch cdl) {

        //Process the edges
        for (int joinedEdge = start; joinedEdge < end; joinedEdge++) {
            // Array goes out of bounds here!
            int neighbourIndex = currentNodeEdges.get(joinedEdge).getNeighbourIndex(currentNode);

            // Only interested in an unvisited neighbour
            if (!this.nodes[neighbourIndex].isVisited()) {
                // Calculate the tentative distance for the neighbour
                int tentative = this.nodes[currentNode].getDistanceFromSource() + currentNodeEdges.get(joinedEdge).getLength();
                // Overwrite if the tentative distance is less than what's currently stored
                if (tentative < nodes[neighbourIndex].getDistanceFromSource()) {
                    nodes[neighbourIndex].setDistanceFromSource(tentative);
                }
            }
        }

        cdl.countDown();
    }

谢谢你迄今为止的帮助

编辑：我添加了堆栈跟踪：

Exception in thread "pool-1-thread-388" java.lang.IndexOutOfBoundsException: Index: 9, Size: 9
    at java.util.ArrayList.rangeCheck(ArrayList.java:657)
    at java.util.ArrayList.get(ArrayList.java:433)
    at ThreadPool.CalculatePerVertice.calculateShortestDistances(CalculatePerVertice.java:136)
    at ThreadPool.CalculatePerVertice$1DijkstraTask.run(CalculatePerVertice.java:76)
    at java.util.concurrent.ThreadPoolExecutor.runWorker(ThreadPoolExecutor.java:1149)
    at java.util.concurrent.ThreadPoolExecutor$Worker.run(ThreadPoolExecutor.java:624)
    at java.lang.Thread.run(Thread.java:748)
    ````