DijkstraのアルゴリズムJava - 距離が正しくない

Question

私はdijkstraのアルゴリズムをコーディングしようとしています。どの頂点から始めても、距離を表示し、ノードのパスを印刷する必要があります。それは頂点2,4、および5で機能しますが、1と3では、それはうんざりします。それはおそらく愚かに小さいものですが、私はそれを見ることができません。

public static void main(String[] args) 
{ 
    int INF = Integer.MAX_VALUE; 
    int verticies = 5; 
    int W[][] = {{INF,7,4,6,1}, 
    {0,INF,0,0,0}, 
    {0,2,INF,4,0}, 
    {0,0,0,INF,0}, 
    {0,0,0,1,INF}}; 

    int startNode = 1; 
    dijkstra(W,verticies,startNode-1); 

} 

public static void dijkstra(int G[][],int n,int startnode) 
{ 
    int INF = Integer.MAX_VALUE, nINF = Integer.MIN_VALUE; 
    //int cost[MAX][MAX],distance[MAX],pred[MAX]; 
    //int visited[MAX],count,mindistance,nextnode,i,j; 
    int cost[][] = new int[n][n]; 
    int distance[] = new int[n]; 
    int pred[] = new int[n]; 
    boolean visited[] = new boolean[n]; 
    int count=0, mindistance=0, nextnode=0,i,j; 

    //pred[] stores the predecessor of each node 
    //count gives the number of nodes seen so far 
    //create the cost matrix 
    for(i=0;i<n;i++) 
     for(j=0;j<n;j++) 
      if(G[i][j]==0) 
       cost[i][j]=INF; 
      else 
       cost[i][j]=G[i][j]; 

    //initialize pred[],distance[] and visited[] 
    for(i=0;i<n;i++) 
    { 
     distance[i]=cost[startnode][i]; 
     pred[i]=startnode; 
     visited[i]=false; 
    } 

    distance[startnode]=0; 
    visited[startnode]=true; 
    count=1; 

    while(count<n-1) 
    { 
     mindistance=INF; 

     //nextnode gives the node at minimum distance 
     for(i=0;i<n;i++) 
      if(distance[i]<mindistance&&!visited[i]) 
      { 
       mindistance=distance[i]; 
       nextnode=i; 
      } 

     //check if a better path exists through nextnode 
     visited[nextnode]=true; 
     for(i=0;i<n;i++) 
      if(!visited[i]) 
       if(mindistance+cost[nextnode][i]<distance[i]) 
       { 
        distance[i]=mindistance+cost[nextnode][i]; 
        pred[i]=nextnode; 
       } 
     count++; 
    } 

    //print the path and distance of each node 
    for(i=0;i<n;i++) 
     if(i!=startnode) 
     { 
      if(distance[i] == INF || distance[i] < 0){ 
       System.out.print("\nNo edge exists between node "+(startnode+1)+" and node "+(i+1)); 
      } else { 
       System.out.format("\nDistance of node %d = %d", (i + 1), distance[i]); 
       System.out.format("\nPath = %d", (i + 1)); 

       j = i; 
       do { 
        j = pred[j]; 
        System.out.format("<-%d", (j + 1)); 
       } while (j != startnode); 
      } 
     } 
} 

Answer 1

私は正確にどのように知りませんが、あなたは何とか自分の計算にINFを得ています。私の疑惑はdistance[i]=mindistance+cost[nextnode][i];行に行きますが、唯一の犯人ではないかもしれませんが、私はチェックしていません。 mindistanceが1（またはそれ以上）でコストがInteger.MAX_VALUEの場合、算術オーバーフローが発生し、結果が負になります。さらなる行動、私は予測していないが、期待通りではない。

あなたがINFを定義する2つの場所で、私は1,000,000の値を変更し、私はあなたのプログラムから、次のような出力が得られます。

Distance of node 2 = 6 
Path = 2<-3<-1 
Distance of node 3 = 4 
Path = 3<-1 
Distance of node 4 = 2 
Path = 4<-5<-1 
Distance of node 5 = 1 
Path = 5<-1 

私はこれが正しいと信じています。

私が見つけた方法は？それは大きな負の数を印刷するとき

 System.out.println("count " + count + " nextnode " + nextnode + " mindistance " + mindistance); 

が、私は算術オーバーフローを疑う開始しました：私はあなたの外側のwhileループの中央にこの文を立ち往生。あなたがデバッガを使用することを学ぶまで、 System.out.println()はあなたのデバッグの友達です。