Priority Queue数据异常排查：Dijkstra算法入队出队数据不符问题

你遇到的问题核心是优先队列的排序逻辑或元素存储顺序完全错误，导致出队的节点和距离不匹配。

从你描述的现象来看：明明入队的是[3,7]（节点3、距离7）和[1,2]（节点1、距离2），但出队得到[1,7]和[3,7]，这说明你的优先队列根本没按距离从小到大排序，反而在按节点编号排序，甚至可能把节点和距离的存储位置搞反了。

必须检查的几个关键点： #

• 优先队列的元素顺序搞反了：Dijkstra算法要求优先队列每次弹出距离最短的节点，正确的存储格式应该是[距离, 节点]，这样默认的小顶堆（比如Java的PriorityQueue）会自动按第一个元素（距离）升序排列。如果你存成了[节点, 距离]，队列会默认按节点编号排序，完全不符合算法要求。
• 自定义比较器写反或未设置：如果一定要用[节点, 距离]的存储顺序，必须手动指定比较器，让队列按距离排序。比如Java里要写：PriorityQueue<int[]> pq = new PriorityQueue<>((a,b) -> a[1] - b[1]);，明确按第二个元素（距离）升序排列。
• 邻接表构建错误：确认times数组的映射逻辑正确——times[i][0]是起始节点，times[i][1]是目标节点，times[i][2]是距离，邻接表应该是adj[起始节点].add(目标节点, 距离)，别把起始和目标搞反。
• 入队操作写错值：遍历起始节点k的邻接节点时，要把[当前计算出的距离, 邻接节点]（或符合比较器要求的顺序）加入队列，别把节点和距离的数值填反。

针对你输入的正确代码片段（Java为例）： #

import java.util.*;

public class NetworkDelay {
    public static void main(String[] args) {
        int[][] times = {{1,2,1},{2,3,7},{1,3,4},{2,1,2}};
        int n = 3, k = 2;
        
        // 构建邻接表
        List<List<int[]>> adj = new ArrayList<>();
        for (int i = 0; i <= n; i++) adj.add(new ArrayList<>());
        for (int[] time : times) {
            int u = time[0];
            int v = time[1];
            int w = time[2];
            adj.get(u).add(new int[]{v, w}); // 起始u -> 目标v，距离w
        }
        
        // 优先队列：按距离升序，存储[距离, 节点]
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        int[] dist = new int[n+1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[k] = 0;
        pq.add(new int[]{0, k}); // 起始节点k的初始距离为0
        
        while (!pq.isEmpty()) {
            int[] curr = pq.poll();
            int currDist = curr[0];
            int node = curr[1];
            
            // 如果当前记录的距离已经比弹出的距离大，直接跳过
            if (currDist > dist[node]) continue;
            
            for (int[] neighbor : adj.get(node)) {
                int nextNode = neighbor[0];
                int nextDist = currDist + neighbor[1];
                // 更新最短距离并入队
                if (nextDist < dist[nextNode]) {
                    dist[nextNode] = nextDist;
                    pq.add(new int[]{nextDist, nextNode});
                }
            }
        }
        
        // 输出结果
        for (int i = 1; i <= n; i++) {
            System.out.println("节点" + i + "的最短距离：" + dist[i]);
        }
    }
}

这段代码里，起始节点2的邻接节点会被正确处理为[7,3]和[2,1]入队，优先队列会先弹出距离最小的[2,1]，完全符合Dijkstra算法的逻辑。

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