优化大型图Dijkstra算法性能：避免优先队列低效操作

import java.util.Arrays;
import java.util.PriorityQueue;

public class DijkstraOptimizer {

    /**
     * 对大型图执行Dijkstra算法，计算从源节点到所有其他节点的最短路径。
     * 优化了优先队列的使用，避免了线性扫描。
     *
     * @param nodeList 节点信息列表。nodeList[0]可能存储纬度，nodeList[1]经度，
     *                 nodeList[2]存储每个节点的出边在edgeList中的起始偏移量。
     *                 nodeList[0].length 表示节点总数。
     * @param edgeList 边信息列表。edgeList[0]源节点ID, edgeList[1]目标节点ID, edgeList[2]边权重。
     *                 这里假定 edgeList[1][i] 是第 i 条边的目标节点，edgeList[2][i] 是第 i 条边的权重。
     * @param sourceNodeId 源节点的ID。
     * @return 包含从源节点到所有其他节点最短距离的数组。
     */
    public static int[] oneToAllArrayOptimized(double[][] nodeList, int[][] edgeList, int sourceNodeId) {
        // 假设 nodeList[0].length 给出节点总数
        int numNodes = nodeList[0].length;
        int[] distance = new int[numNodes];

        // 1. 正确初始化距离数组：所有节点距离设为“无穷大”，源节点为0
        Arrays.fill(distance, Integer.MAX_VALUE);
        distance[sourceNodeId] = 0;

        // 优先队列存储 [节点ID, 当前到该节点的最短距离]
        // 按照距离升序排列
        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 u = current[0]; // 当前处理的节点ID
            int dist_u = current[1]; // 当前到节点u的距离

            // 2. 惰性删除：如果从队列中取出的路径比已知的最短路径长，则跳过
            if (dist_u > distance[u]) {
                continue;
            }

            // 获取节点u的出边范围
            int offsetStart;
            int offsetEnd;
            // 假设 nodeList[2] 存储了每个节点的出边偏移量
            if (u == numNodes - 1) {
                offsetStart = (int) nodeList[2][u];
                offsetEnd = edgeList[0].length; // 最后一个节点的出边到edgeList末尾
            } else {
                offsetStart = (int) nodeList[2][u];
                offsetEnd = (int) nodeList[2][u + 1];
            }

            // 遍历节点u的所有出边
            for (int i = offsetStart; i < offsetEnd; i++) {
                int v = edgeList[1][i]; // 目标节点ID
                int weight_uv = edgeList[2][i]; // 边u->v的权重

                // 检查是否会发生溢出，并更新最短路径
                // distance[u] == Integer.MAX_VALUE 表示 u 不可达，则任何通过 u 的路径都不可达
                if (distance[u] != Integer.MAX_VALUE && 
                    // 确保 weight_uv 不是 Integer.MAX_VALUE，避免溢出
                    weight_uv != Integer.MAX_VALUE && 
                    (long)distance[u] + weight_uv < distance[v]) { // 使用long进行中间计算避免溢出

                    distance[v] = distance[u] + weight_uv;
                    // 3. 直接添加新路径到优先队列，不进行查找和删除
                    prioQueue.add(new int[]{v, distance[v]});
                }
            }
        }
        return distance;
    }
}