我正在尝试为 class 实现 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

祝你有个愉快的一天~~

我正在尝试为 class 实现 dijkstra 算法

I am trying to implement dijkstra's algorithm for a class

c

dijkstra

shortest-path