我的Java实现Dijkstra算法未通过测试用例，请求排查问题

问题点分析 #

• 无效路径跳过时机错误：原代码中跳过无效路径的判断放在计算邻居新距离之后，会导致过时路径仍去处理邻居，既浪费资源也可能引发逻辑错误。正确做法是弹出节点后立即检查，若当前路径并非已知最短路径，直接跳过该节点的所有处理。
• 整数溢出风险：当节点当前距离为Integer.MAX_VALUE时，加上邻居权重会触发整数溢出，结果变为负数，会错误判定该负数小于邻居当前距离，进而错误更新距离。需提前判断当前节点距离是否为最大值，避免溢出。
• 起始节点硬编码：main方法固定起始节点为0，若测试用例节点编号不从0开始，会导致计算结果错误，建议改为从输入读取起始节点。

修正后的代码 #

import java.util.*;

class Graph {
    Map<Integer, List<Edge>> adjacencyList;

    public Graph() {
        adjacencyList = new HashMap<>();
    }

    public void addEdge(int source, int destination, int weight) {
        adjacencyList.putIfAbsent(source, new ArrayList<>());
        adjacencyList.putIfAbsent(destination, new ArrayList<>());
        adjacencyList.get(source).add(new Edge(destination, weight));
        adjacencyList.get(destination).add(new Edge(source, weight));
    }

    public Map<Integer, Integer> dij(int start) {
        PriorityQueue<Edge> pq = new PriorityQueue<>(Comparator.comparingInt(edge -> edge.weight));
        Map<Integer, Integer> distances = new HashMap<>();

        // 初始化所有节点距离为最大值
        for (Integer node : adjacencyList.keySet()) {
            distances.put(node, Integer.MAX_VALUE);
        }
        distances.put(start, 0);
        pq.add(new Edge(start, 0));

        while (!pq.isEmpty()) {
            Edge curr = pq.poll();
            int currNode = curr.node;
            int currDist = curr.weight;

            // 关键：若当前路径不是已知最短路径，直接跳过
            if (currDist > distances.get(currNode)) {
                continue;
            }

            // 避免当前节点不可达时的整数溢出
            if (distances.get(currNode) == Integer.MAX_VALUE) {
                continue;
            }

            for (Edge neighbour : adjacencyList.getOrDefault(currNode, new ArrayList<>())) {
                int newDist = distances.get(currNode) + neighbour.weight;
                if (newDist < distances.get(neighbour.node)) {
                    distances.put(neighbour.node, newDist);
                    pq.add(new Edge(neighbour.node, newDist));
                }
            }
        }
        return distances;
    }
}

class Edge {
    int node;
    int weight;

    public Edge(int node, int weight) {
        this.node = node;
        this.weight = weight;
    }

    // 可选：重写toString方便调试
    @Override
    public String toString() {
        return "Edge{" + "node=" + node + ", weight=" + weight + '}';
    }
}

public class Solution {
    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        int V = s.nextInt();
        int E = s.nextInt();
        Graph graph = new Graph();
        for (int i = 0; i < E; i++) {
            int ei = s.nextInt();
            int ej = s.nextInt();
            int w = s.nextInt();
            graph.addEdge(ei, ej, w);
        }
        // 从输入读取起始节点，适配更多测试用例
        int start = s.nextInt();

        Map<Integer, Integer> ans = graph.dij(start);

        // 按节点排序输出，结果更直观
        List<Integer> sortedNodes = new ArrayList<>(ans.keySet());
        Collections.sort(sortedNodes);
        for (Integer node : sortedNodes) {
            System.out.println(node + " " + ans.get(node));
        }
        s.close();
    }
}

关键修正说明 #

1. 将无效路径跳过逻辑移至弹出节点后立即执行，避免无效计算。
2. 增加节点可达性判断，防止整数溢出导致的错误更新。
3. 修改main方法，支持从输入读取起始节点，适配不同测试场景。
4. 新增Edge类的toString方法，便于调试过程中查看队列内容。
5. 输出前对节点排序，让结果展示更有序直观。

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