私はクラスのdijkstraのアルゴリズムを実装しようとしています

Question

私はコストのための出力として0-3-6-5を得ることになっています。前の配列の出力は-1-0-3-1です。訪問配列の場合は1-1-1-1です。

私の出力には0-3-7-5、コストは-1-0-1-1です。可能であればお手伝いください。

私は7が6でなければならない場所を知ろうとしましたが、わかりません。私がC言語でコーディングしたのはこれが初めてです。

#include <stdlib.h> 
#include <stdio.h> 
#include <math.h> 
#define infinity 999 

int main (void){ 

    int dij[4][4] = {{0,3,8,6}, 
     {3,0,4,2}, 
     {8,4,0,1}, 
     {6,2,1,0}}; 

    int visit[4]; 
    int cost[4]; 
    int previous[4]; 

    //filling the visit, cost, previous arrays 
    for(int j=0; j<4; j++){ 
     visit[j] = 0; 
     cost[j] = infinity; 
     previous[j] = -1; 
    }//adding the values to the arrays  
    //node I am on 
    cost[0] = 0; //first position in the cost array is set to 0 
    int counter = 0; //counter for the while loop  
    int currentRow = 0; //checks for the rows holding th smallest value in the dij array 
     while(counter < 4){ 
       int min = infinity; //min value is set to infinity at the beginning of program    
       for(int y=0; y<4; y++){     
        //if the cost at the current position in th cost array is < min and the node is not visited 
        if(cost[y] < min && visit[y] == 0){ 
         min = cost[y]; 
         currentRow = y; 
        }//if      
        visit[currentRow] = 1; 
       }//for loop for col of dij array. 
       //loop to look at the cost array to find the lowest cost unvisited node and set row to that index value 
       for(int x=0; x<4; x++){      
        if(visit[x] != 1){    
         if(min + dij[currentRow][x] < cost[x]){ 
          cost[x] = min + dij[currentRow][x]; 
          previous[x] = currentRow; 
         } 
        } 
       } 
       counter++; 
     }//while loop for x column of dij array. 

Answer 1

あなたの訪問フラグはforステートメントの外側でなければなりません。訪問フラグは反復時間になければならないからです。

for(int y=0; y<4; y++){     

    if(cost[y] <= min && visit[y] == 0){ 
     min = cost[y]; 
     currentRow = y; 
    }//if      
    //<-- not here 
}//for loop for col of dij array. 

visit[currentRow] = 1; 

ここには、印刷値を持つ完全なソースコードがあります。

#include <stdlib.h> 
#include <stdio.h> 
#include <math.h> 
#define infinity 999 

int main (void) 
{ 

    int dij[4][4] = { 
     {0,3,8,6}, 
     {3,0,4,2}, 
     {8,4,0,1}, 
     {6,2,1,0} 
    }; 

    int visit[4]; 
    int cost[4]; 
    int previous[4]; 

    //filling the visit, cost, previous arrays 
    for(int j=0; j<4; j++){ 
     visit[j] = 0; 
     cost[j] = infinity; 
     previous[j] = -1; 
    }//adding the values to the arrays  

    //node I am on 
    cost[0] = 0; //first position in the cost array is set to 0 
    int counter = 0; //counter for the while loop  
    int currentRow = 0; //checks for the rows holding th smallest value in the dij array 

    while(counter < 4) 
    { 
     int min = infinity; //min value is set to infinity at the beginning of program    
     for(int y=0; y<4; y++){     
      //if the cost at the current position in th cost array is < min and the node is not visited 
      if(cost[y] <= min && visit[y] == 0){ 
       min = cost[y]; 
       currentRow = y; 
      }//if      

     }//for loop for col of dij array. 

     visit[currentRow] = 1; 

     //loop to look at the cost array to find the lowest cost unvisited node and set row to that index value 
     for(int x=0; x<4; x++){ 

      if(visit[x] != 1 && cost[currentRow] + dij[currentRow][x] < cost[x] && cost[currentRow] != infinity) 
      {    
       //if(min + dij[currentRow][x] < cost[x]) 
       { 
        cost[x] = cost[currentRow] + dij[currentRow][x]; 
        previous[x] = currentRow; 
       } 
      } 
     } 

     counter++; 
    }//while loop for x column of dij array. 


    printf("visit cost previous \n"); 

    for(int j=0; j<4; j++){ 
     printf("%d \t %d \t %d \n", visit[j], cost[j], previous[j]); 
    }//adding the values to the arrays 

    return 0; 
} 

次のように出力があるべき、

visit cost previous 
1  0  -1 
1  3  0 
1  6  3 
1  5  1 

は素敵な一日~~