尝试实现 dijkstra 算法（运行进入我无法完全修复的线程中的异常）

Question

我必须执行 dijkstra 算法以找到与道路相连的各个城市之间的最短路径。每条路都有固定的成本，每个城市都有固定的停留成本。分配只是为了找到第一个和第二个节点之间的最短路径，最少有 3 个节点，但我写我的是为了找到源和所有节点之间的最短路径。

输入数据首先给出城市（节点）数，然后给出道路数（links）。然后每个城市（节点）都以“#citie cost”的格式读入它的成本。然后 links 被读入为“#first_city #second_city cost”。我将它们存储在一个二维数组中，其中第一个维度是城市，第二个维度是从每个城市到其他城市的旅行成本。我最初在没有 link 初始化为 null 的城市之间有成本，但我开始得到我目前正在处理的异常。

下面是我输入数据的方式：

private Integer num_cities;
private Integer num_roads;

public static void main(String[] args) {

        test p = new test();
        

        p.num_cities = readInt();
        p.num_roads = readInt();

        Integer [][] roads = new Integer[p.num_cities][p.num_roads];

        Integer [] hotel_cost = new Integer[p.num_cities];

        //Reading in Hotel Costs at Each City
        hotel_cost[0] = 0;
        hotel_cost[1] = 0;
        for (Integer i = 2; i < p.num_cities; i++) {
            Integer hotel = readInt() - 1;
            hotel_cost[hotel] = readInt();
        }

        //filling with no connections
        for (Integer i = 1; i < p.num_cities; i++) {
            for (Integer j = 0; j < p.num_roads; j++) {
                roads[i][j] = 0;
            }
        }

        //Reading in Gas Costs on Each Road
        for (Integer i = 0; i < p.num_roads; i++) {
            Integer a = readInt() - 1;
            Integer b = readInt() - 1;
            Integer cost = readInt();
            roads[a][b] = cost;
            roads[b][a] = cost;
        }

        p.dijkstra(roads, hotel_cost, 0);
    
    
    }
}

我当前的 dijkstra 函数定义如下：

    public Integer minDistance(Integer cost[], Boolean b[]) {
        Integer min = Integer.MAX_VALUE, index = -1;
        for (Integer x = 0; x < num_cities; x++) {
            if (b[x] == false && cost[x] <= min) {
                min = cost[x];
                index = x;
            }
        }
        return index;
    }


    public void dijkstra(Integer roads[][], Integer hotel_cost[], Integer src) {

        Integer cost[] = new Integer[num_cities];

        Boolean b[] = new Boolean[num_cities];

        for(Integer i = 0; i < num_cities; i++) {
            cost[i] = Integer.MAX_VALUE;
            b[i] = false;
        }

        cost[src] = 0;
        for (Integer count = 0; count < num_cities; count++) {
            Integer u = minDistance(cost, b);
            b[u] = true;
            for (Integer x = 0; x < num_roads; x++) {
                if (!b[x] && (roads[u][x] + hotel_cost[u]) != 0 && cost[u] != Integer.MAX_VALUE && cost[u] + roads[u][x] + hotel_cost[u] < cost[x] ) {
                    cost[x] = cost[u] + roads[u][x] + hotel_cost[x];
                }
            }
        }
        printCostChart(cost, num_cities);
    }

我不断收到以下异常：

Exception in thread "main" java.lang.NullPointerException
        at cmsc401.dijkstra(cmsc401.java:72)
        at cmsc401.main(cmsc401.java:116)

我当前的测试输入是：

从第一个节点到第二个节点的旅行成本的正确输出应该是 388 美元。

我测试了一些主要试图隔离异常的东西，它似乎在 if 语句的这一部分：

!b[x] && (roads[u][x] + hotel_cost[u]) != 0

如果你想测试它，我可以 post github link 但我更愿意将内容保密以停止任何复制。

Answer 1

正如我在评论中所述，我不得不猜测，但我假设尝试拆箱roads[u][x]会引发 NPE。

为什么？因为你这样初始化它：

for (Integer i = 1; i < p.num_cities; i++) {
   for (Integer j = 0; j < p.num_roads; j++) {
      roads[i][j] = 0;
   }
}

如您所见，roads[0][j] 可能永远不会被初始化，因此只要 u 为 0，您就会得到 NPE，因为 roads[0] 中的所有元素仍然为空。

您有一个设置 roads[a][b] 等的循环（注释为“//阅读每条道路的汽油成本”）但是由于 a 和 b 设置为 readInt() - 1; 那些也可能永远不会是 0（至少由于缺少代码我无法分辨）。

TLDR： 在某些情况下使用 Integer 和 Boolean 等原始包装器（或这些包装器的数组）时，您可能很难发现和理解 NullPointerExceptions其中需要原语（int、boolean 等）并且自动拆箱尝试将 null 转换为原语。

尝试实现 dijkstra 算法（运行进入我无法完全修复的线程中的异常）

Trying to Implement dijkstra's algorithm (Running into Exception in thread that I can't quite fix)

java

computer-science

dijkstra

nullpointerexception

尝试实现 dijkstra 算法（运行 进入我无法完全修复的线程中的异常）

Trying to Implement dijkstra's algorithm (Running into Exception in thread that I can't quite fix)

java

computer-science

dijkstra

nullpointerexception

尝试实现 dijkstra 算法（运行进入我无法完全修复的线程中的异常）