Dijkstra的算法实现使用类

-3

我试图解决HackerRank上的问题，我试着解决它，我发现它给-2149088距离虽然有一个问题，我的逻辑最重要的while循环.can任何人都指出我的错误即小白菜:)谢谢。链接问题的陈述HackerRank：https://www.hackerrank.com/challenges/dijkstrashortreach Dijkstra的算法实现使用类

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); 
    } 
}

来源

2015-10-01 SSR

“不知道我的代码出了什么问题”太模糊了。你应该尝试集中你的问题，而不是倾销代码，并写下“它不工作”.... – alfasin

明白了！事情是我忘了没有附加到图上的节点。所以我不得不在代码中将“q”设置为无穷大的dist设置为0。谢谢各位 – SSR

如果您设置DIST为Integer.MAX_VALUE，然后点击此处查看：

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

        }

然后节点[J] .dist总是小于q更大。 dist + adj [id] [j]，因为MAX_VALUE + adj [id] [j] < 0.您有一个整数溢出并将溢出的值分配给节点[j] .dist。

我希望它有帮助。

来源

2015-10-01 17:07:24

非常感谢！ Ť – SSR

Dijkstra的算法实现使用类

回答

相关问题