修改Dijkstra算法解决终点路径数问题的边界案例修复求助

我在实现修改版Dijkstra算法解决"到达目的地的路径数"问题时，代码通过了16个测试用例中的12个，但在处理边权全为1e9的测试用例时出错。

原代码 #

class Pair {
    int first;
    int second;
    public Pair(int first, int second) {
        this.first = first;
        this.second = second;
    }
}
class Solution {

    static int countPaths(int n, List < List < Integer >> roads) {
        
        // 创建邻接表
        ArrayList < ArrayList < Pair >> adj = new ArrayList < > ();
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList < > ());
        }
        int m = roads.size();
        for (int i = 0; i < m; i++) {
            adj.get(roads.get(i).get(0)).add(new Pair(roads.get(i).get(1), roads.get(i).get(2)));
            adj.get(roads.get(i).get(1)).add(new Pair(roads.get(i).get(0), roads.get(i).get(2)));
        }

        // 定义最小堆优先队列
        PriorityQueue < Pair > pq = new PriorityQueue < Pair > ((x, y) -> x.first - y.first);

        // 初始化距离数组和路径数数组
        int[] dist = new int[n];
        int[] ways = new int[n];
        for (int i = 0; i < n; i++) {
            dist[i] = (int) 1e9;
            ways[i] = 0;
        }
        dist[0] = 0;
        ways[0] = 1;
        pq.add(new Pair(0, 0));

        int mod = (int)(1e9 + 7);

        // Dijkstra算法主循环
        while (pq.size() != 0) {
            int dis = pq.peek().first;
            int node = pq.peek().second;
            pq.remove();

            for (Pair it : adj.get(node)) {
                int adjNode = it.first;
                int edW = it.second;

                if (dis + edW < dist[adjNode]) {
                    dist[adjNode] = dis + edW;
                    pq.add(new Pair(dis + edW, adjNode));
                    ways[adjNode] = ways[node];
                } else if (dis + edW == dist[adjNode]) {
                    ways[adjNode] = (ways[adjNode] + ways[node]) % mod;
                }
            }
        }
        return ways[n - 1] % mod;
    }
}

出错的测试用例 #

输入：

6 8
0 1 1000000000
0 3 1000000000
1 3 1000000000
1 2 1000000000
1 5 1000000000
3 4 1000000000
4 5 1000000000
2 5 1000000000

• 输出结果：0
• 预期结果：1

问题原因 #

整数溢出。Java中int类型的最大值是2147483647，而1e9已经接近这个值。当计算dis + edW时，两个1e9相加会超过int的上限，导致溢出变成负数。此时dis + edW < dist[adjNode]的判断会错误地认为这个负数距离比初始化的1e9更小，后续的路径数更新逻辑完全混乱，最终得到错误的结果。

修复方案 #

将所有存储距离的变量从int改为long，利用long更大的数值范围（最大值9e18）避免溢出问题。

修改后的完整代码 #

class Pair {
    long first; // 存储距离，改为long
    int second; // 存储节点，保持int
    public Pair(long first, int second) {
        this.first = first;
        this.second = second;
    }
}
class Solution {

    static int countPaths(int n, List < List < Integer >> roads) {
        
        ArrayList < ArrayList < Pair >> adj = new ArrayList < > ();
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList < > ());
        }
        int m = roads.size();
        for (int i = 0; i < m; i++) {
            int u = roads.get(i).get(0);
            int v = roads.get(i).get(1);
            long w = roads.get(i).get(2); // 边权转为long
            adj.get(u).add(new Pair(w, v));
            adj.get(v).add(new Pair(w, u));
        }

        // 优先队列的比较器改为比较long类型的距离
        PriorityQueue < Pair > pq = new PriorityQueue < Pair > ((x, y) -> Long.compare(x.first, y.first));

        long[] dist = new long[n]; // 距离数组改为long[]
        int[] ways = new int[n];
        for (int i = 0; i < n; i++) {
            dist[i] = (long)1e18; // 初始化更大的数值，避免和有效距离冲突
            ways[i] = 0;
        }
        dist[0] = 0;
        ways[0] = 1;
        pq.add(new Pair(0, 0));

        int mod = (int)(1e9 + 7);

        while (pq.size() != 0) {
            long dis = pq.peek().first;
            int node = pq.peek().second;
            pq.remove();

            // 如果当前取出的距离已经大于已知的最短距离，跳过该节点
            if (dis > dist[node]) continue;

            for (Pair it : adj.get(node)) {
                long edW = it.first;
                int adjNode = it.second;

                if (dis + edW < dist[adjNode]) {
                    dist[adjNode] = dis + edW;
                    pq.add(new Pair(dist[adjNode], adjNode));
                    ways[adjNode] = ways[node];
                } else if (dis + edW == dist[adjNode]) {
                    ways[adjNode] = (ways[adjNode] + ways[node]) % mod;
                }
            }
        }
        return ways[n - 1] % mod;
    }
}

关键修改点 #

1. Pair类：调整字段含义，first存储边权/距离（改为long类型），second存储节点
2. 距离数组：dist数组从int[]改为long[]，初始化值改为1e18（远大于可能的最大路径距离）
3. 优先队列比较器：使用Long.compare()替代int减法，避免比较时溢出
4. 距离计算：所有涉及路径距离的计算都用long类型进行，确保数值不溢出
5. 新增跳过逻辑：当取出的队列元素距离大于已知最短距离时，直接跳过，避免重复处理无效节点

修复效果 #

修改后，大边权的测试用例中距离计算不再溢出，路径数的更新逻辑正常执行，能得到正确的预期结果1，同时不会影响其他测试用例的正确性。

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