Dijkstra算法实现LeetCode Network Delay Time部分用例不通过求排查

• 核心错误：Java PriorityQueue 不支持动态更新元素优先级
  你在初始化阶段将所有节点一次性加入最小堆，即便你自定义的比较器会实时读取distFromSource的当前值，但Java的PriorityQueue为静态二叉堆结构，仅会在元素入堆、出堆时做局部调整，不会因为你后续修改了distFromSource中节点的距离值，就自动重新调整所有已入堆元素的排序位置。这导致堆顶弹出的节点并非当前全局最短距离的节点，完全违背了Dijkstra算法的贪心选择逻辑，是代码通过率低的核心原因。
• 潜在问题：整数溢出风险
  若当前处理节点的最短距离为Integer.MAX_VALUE，直接加上边权值会发生整数溢出得到负数，此时alternativeDist < distFromSource.get(destination)的判断会误判为真，导致距离计算完全错误。
• 冗余设计：提前加载所有节点入堆无必要
  Dijkstra算法的最小堆仅需存储已经触达、待处理的节点即可，提前把所有节点（包括不可达节点）加载进堆只会增加无意义的运行开销。

调整最小堆的使用逻辑，改为每次发现更短路径时将新的<距离, 节点>对插入堆，不需要维护堆内的旧记录，弹出时判断当前记录是否过时即可，具体改动如下：

1. 最小堆存储结构改为Pair<Integer, Integer>，第一个值为节点距离起点的距离，第二个值为节点编号，排序规则按距离升序
2. 初始化仅将起点（距离为0）加入堆，无需提前加载所有节点
3. 移除visited集合，弹出堆顶元素时，若堆中存储的距离大于该节点已记录的最短距离，说明该条记录为过时数据，直接跳过即可
4. 计算新路径距离前先判断当前节点的距离是否为Integer.MAX_VALUE，避免整数溢出

修正后参考代码 #

class Solution {
    public int networkDelayTime(int[][] times, int n, int k) {
        // 构建邻接表
        HashMap<Integer, HashSet<Pair<Integer, Integer>>> adjacencyList = new HashMap<>();
        for (int[] time : times) {
            int source = time[0];
            int target = time[1];
            int travelTime = time[2];
            adjacencyList.computeIfAbsent(source, key -> new HashSet<>())
                    .add(new Pair<>(target, travelTime));
        }

        // 初始化距离数组
        HashMap<Integer, Integer> distFromSource = new HashMap<>();
        for (int i = 1; i <= n; i++) {
            distFromSource.put(i, Integer.MAX_VALUE);
        }
        distFromSource.put(k, 0);

        // 最小堆存储<距离, 节点>
        PriorityQueue<Pair<Integer, Integer>> minHeap = new PriorityQueue<>((p1, p2) -> p1.getKey() - p2.getKey());
        minHeap.add(new Pair<>(0, k));

        while (!minHeap.isEmpty()) {
            Pair<Integer, Integer> curr = minHeap.poll();
            int currDist = curr.getKey();
            int currNode = curr.getValue();

            // 过时记录直接跳过
            if (currDist > distFromSource.get(currNode)) {
                continue;
            }
            // 不可达节点直接跳过，避免溢出
            if (currDist == Integer.MAX_VALUE) {
                break;
            }

            // 遍历邻边
            for (Pair<Integer, Integer> edge : adjacencyList.getOrDefault(currNode, new HashSet<>())) {
                int dest = edge.getKey();
                int weight = edge.getValue();
                int newDist = currDist + weight;
                if (newDist < distFromSource.get(dest)) {
                    distFromSource.put(dest, newDist);
                    minHeap.add(new Pair<>(newDist, dest));
                }
            }
        }

        // 计算最大延迟
        int maxDistance = Integer.MIN_VALUE;
        for (int dist : distFromSource.values()) {
            if (dist == Integer.MAX_VALUE) {
                return -1;
            }
            maxDistance = Math.max(maxDistance, dist);
        }
        return maxDistance;
    }
}

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