Dijkstra算法处理超大规模图过慢问题排查求助

我需要在包含2500万个节点的大规模图上执行Dijkstra算法，图的存储结构如下：

• 节点：二维数组double[][] nodeList，每个节点是double[]，包含纬度、经度、偏移量（该节点第一条出边的索引）
• 边：二维数组int[][] edgeList，每条边是int[]，包含源节点ID、目标节点ID、权重

当前代码能得到正确结果，但在笔记本上执行耗时约8分钟，远达不到15秒的要求。我用int[]作为优先级队列的比较元组，想请教：

• 算法是否存在本质低效问题？
• 是否选错了数据结构？
• 有没有遗漏的优化点？

附原代码：

public static int[] oneToAllArray(double[][]nodeList, int[][]edgeList,int sourceNodeId) {
        int[] distance = new int[nodeList[0].length]; //the array that will be returned
        //the priorityQueue will use arrays with the length 2, representing [index, weight] for each node and order them by their weight
        PriorityQueue<int[]> prioQueue = new PriorityQueue<>((a, b) -> ((int[])a)[1] - ((int[])b)[1]);
        int offset1; //used for determining the amount of outgoing edges
        int offset2;
        int newWeight; //declared here so we dont need to declare it a lot of times later (not sure if that makes a difference)
        //currentSourceNode here means the node that will be looked at for OUTGOING edges
        int[] currentSourceNode= {sourceNodeId,0};
        prioQueue.add(currentSourceNode); 
        //at the start we only add the sourceNode, then we start the actual algorithm
        
        while(!prioQueue.isEmpty()) {
            if(prioQueue.size() % 55 == 2) {
                System.out.println(prioQueue.size());
            }
            
            currentSourceNode=prioQueue.poll();
            int sourceIndex = currentSourceNode[0];
            
            if(sourceIndex == nodeList[0].length-1) {
                offset1= (int) nodeList[2][sourceIndex];
                offset2= edgeList[0].length;
            } else {
                offset1= (int) nodeList[2][sourceIndex];
                offset2= (int) nodeList[2][sourceIndex+1];
            }
            //checking every outgoing edge for the currentNode
            for(int i=offset1;i<offset2;i++) {
                int targetIndex = edgeList[1][i];
                
                //if the node hasnt been looked at yet, the weight is just the weight of this edge + distance to sourceNode
                if(distance[targetIndex]==0&&targetIndex!=sourceNodeId) {
                    distance[targetIndex] = distance[sourceIndex] + edgeList[2][i];
                    int[]targetArray = {targetIndex, distance[targetIndex]};
                    prioQueue.add(targetArray);
                } else if(prioQueue.stream().anyMatch(e -> e[0]==targetIndex)) {
                    //above else if checks if this index is already in the prioQueue
                    newWeight=distance[sourceIndex]+edgeList[2][i];
                    //if new weight is better, we have to update the distance + the prio queue
                    if(newWeight<distance[targetIndex]) {
                        distance[targetIndex]=newWeight;
                        int[] targetArray;
                        targetArray=prioQueue.stream().filter(e->e[0]==targetIndex).toList().get(0);
                        prioQueue.remove(targetArray);
                        targetArray[1]=newWeight;
                        prioQueue.add(targetArray);
                    }
                    
                }
                
            }
            
            
            
        }
        
        
        
        return distance;
    }

核心性能问题分析 #

1. 优先级队列的低效操作

   • 用stream().anyMatch()和stream().filter()查找队列中的节点，都是**O(n)**复杂度，大规模图下每次遍历队列都会带来巨大开销，这是耗时的核心原因。
   • Java标准PriorityQueue不支持高效的元素更新，修改队列元素权重再重新入队的方式，会导致队列中堆积大量重复节点，拖慢poll()操作效率。

2. 距离数组的逻辑错误

   • 用distance[targetIndex]==0判断节点是否未访问，会和源节点的初始距离0冲突，且无法处理目标节点真实距离为0的情况。正确的初始值应该设为无穷大（如Integer.MAX_VALUE）。
   • 没有跳过已经处理过的节点（即从队列中poll出的节点，其记录的距离大于已确认的最短距离），导致重复计算。

3. 不必要的IO操作

   • 循环中频繁触发System.out.println()打印队列大小，IO操作在大规模计算中开销极高，直接拖慢整体速度。

优化方案 #

1. 采用「延迟删除」策略优化优先级队列

   • 不再查找和删除队列中的旧节点，直接将新的（节点ID，更新后距离）元组加入队列。当poll出节点时，先检查队列中的距离是否大于已知的最短距离，若是则直接跳过该节点的处理。
   • 所有队列操作变为O(log n)，彻底避免O(n)的遍历开销。

2. 修正距离数组的初始化与状态判断

   • 初始化distance数组时，将所有元素设为Integer.MAX_VALUE，仅源节点设为0。
   • poll出节点后，先判断currentDist > distance[sourceIndex]，若是则跳过后续处理，避免重复计算。

3. 减少对象创建与GC压力

   • 原代码每次循环创建新int[]，可考虑复用对象或用自定义静态内部类存储（节点ID，距离），降低内存开销。

优化后的代码示例 #

public static int[] oneToAllArray(double[][] nodeList, int[][] edgeList, int sourceNodeId) {
    int nodeCount = nodeList[0].length;
    int[] distance = new int[nodeCount];
    
    // 初始化距离数组为无穷大，源节点距离设为0
    for (int i = 0; i < nodeCount; i++) {
        distance[i] = Integer.MAX_VALUE;
    }
    distance[sourceNodeId] = 0;

    // 优先级队列：按距离升序排列
    PriorityQueue<int[]> prioQueue = new PriorityQueue<>((a, b) -> a[1] - b[1]);
    prioQueue.add(new int[]{sourceNodeId, 0});

    while (!prioQueue.isEmpty()) {
        int[] current = prioQueue.poll();
        int sourceIndex = current[0];
        int currentDist = current[1];

        // 当前队列中的距离已过时，直接跳过
        if (currentDist > distance[sourceIndex]) {
            continue;
        }

        // 获取当前节点的出边范围
        int offset1 = (int) nodeList[2][sourceIndex];
        int offset2 = (sourceIndex == nodeCount - 1) ? edgeList[0].length : (int) nodeList[2][sourceIndex + 1];

        // 遍历所有出边
        for (int i = offset1; i < offset2; i++) {
            int targetIndex = edgeList[1][i];
            int edgeWeight = edgeList[2][i];

            // 计算新距离，避免溢出
            if (currentDist != Integer.MAX_VALUE && currentDist + edgeWeight < distance[targetIndex]) {
                distance[targetIndex] = currentDist + edgeWeight;
                prioQueue.add(new int[]{targetIndex, distance[targetIndex]});
            }
        }
    }

    return distance;
}

额外优化建议 #

• 内存优化：若边数量极大，可改用ByteBuffer等原始类型缓冲区存储数据，减少内存占用与缓存命中失败。
• 并行优化：利用多核心CPU实现并行Dijkstra，比如拆分图的区域并行计算，注意线程安全。
• 硬件优化：确保图数据能完全加载到内存中，若内存不足可使用SSD存储减少磁盘IO开销。

内容的提问来源于stack exchange，提问作者christof