我正在嘗試實現類Dijkstra的算法

Question

我應該得到0-3-6-5作爲成本的輸出。 -1-0-3-1用於前一個數組的輸出。和1-1-1-1爲訪問數組。

我得到了0-3-7-5爲我的輸出成本和-1-0-1-1爲以前。如果可以的話請幫忙。

我試圖看看7是什麼時候它應該是一個六，而我沒有搞清楚。這是我第一次用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 

有一個愉快的一天~~