클래스에 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 

좋은 일이 ~ ~