使用类的 Dijkstra 算法实现

Question

我正在尝试解决 HackerRank 上的一个问题，我已经尝试解决它，但我发现它给出了类似 -2149088 的距离，尽管我的逻辑在 while 循环中最重要的是有问题。有人能指出来吗我的错误是菜鸟 :) 谢谢。 Link 问题陈述 HackerRank : https://www.hackerrank.com/challenges/dijkstrashortreach

import java.io.*;  
import java.util.*;  
import java.math.*;

public class Solution {

public static void main(String[] args) {

    Scanner in = new Scanner (System.in);
    int cases = in.nextInt();

    for(int i=0; i<cases; i++){
        int N = in.nextInt();
        int M = in.nextInt();
        int adj[][] = new int[N+1][N+1];

        Node nodes[] = new Node[N+1];

        for(int k=1; k<=N; k++)
           nodes[k] = new Node(k);    


        for(int j=0; j<=N; j++)
            for(int k=0; k<=N; k++)
                adj[j][k] = Integer.MAX_VALUE;


        for(int j=0; j<M; j++){

            int A = in.nextInt();
            int B = in.nextInt();
            int W = in.nextInt();

            adj[A][B] = Math.min(W,adj[A][B]);
            adj[B][A] = Math.min(W,adj[A][B]);
        }

        int S = in.nextInt();

        nodes[S].dist = 0;
        PriorityQueue<Node> que = new  PriorityQueue<Node>();

        for(int k=1; k<=N; k++)
            que.add(nodes[k]);


        while(!que.isEmpty()){
            Node q = que.poll();
            int id = q.ID;

            for(int j=1; j<=N; j++){
                if(adj[id][j] != Integer.MAX_VALUE){
                     System.out.println(""+q.dist);
                    if(nodes[j].dist>q.dist+adj[id][j]){
                      nodes[j].dist = q.dist+adj[id][j];

                    } 
                }
            }
        }

        for(int j=1; j<=N; j++){
            if(nodes[j].dist==Integer.MAX_VALUE){System.out.println("-1");}
            else if(nodes[j].dist!=0) {System.out.print(nodes[j].dist+" ");}
        }
    }

}

}

class Node implements Comparable<Node>{

    public int dist;
    public int ID;

    public Node(int getID){
        this.ID = getID;
        dist = Integer.MAX_VALUE;
    }    


    @Override
    public int compareTo (Node node) {
        return Integer.valueOf(this.dist).compareTo(node.dist);
    }   
}

Answer 1

如果您将 dist 设置为 Integer.MAX_VALUE，然后在此处查看：

                    if(nodes[j].dist>q.dist+adj[id][j]){
                      nodes[j].dist = q.dist+adj[id][j];

                    }

那么 nodes[j].dist 总是大于 q.dist+adj[id][j]，因为 MAX_VALUE + adj[id][j] < 0。你有整数溢出并将溢出的值分配给 nodes[j].dist.

希望对您有所帮助。

使用类的 Dijkstra 算法实现

Dijkstra's Algorithm Implementation using classes

java

algorithm

dijkstra

graph-algorithm

使用 类 的 Dijkstra 算法实现

Dijkstra's Algorithm Implementation using classes

java

algorithm

dijkstra

graph-algorithm

使用类的 Dijkstra 算法实现