J'essaye de mettre en application l'algorithme de dijkstra pour une classe

Question

Je suis censé obtenir 0-3-6-5 comme production pour le coût. -1-0-3-1 pour la sortie du tableau précédent. et 1-1-1-1 pour le tableau de visite. Je reçois 0-3-7-5 pour ma sortie dans le coût et -1-0-1-1 pour le précédent. S'il vous plait aidez si vous le pouvez.

J'ai essayé de voir d'où le 7 vient quand il devrait être un six et je ne le découvre pas. C'est la première fois que j'ai codé en langage C, donc cela peut sembler un peu bâclé.

#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

Votre indicateur de visite doit être en dehors des instructions for. Parce que le drapeau de visite doit être au moment de l'itération.

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; 

Voici le code source complet avec des valeurs d'impression.

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

La sortie devrait être la suivante,

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

Bonne journée ~~