arrays - Dijkstra 算法

Question

我正在尝试使用具有内存分配的双数组在 C 中实现 dijkstra 算法（在大图中解决它），但我还不能让它运行。我的代码没有出现任何错误，只是所有答案都是 0。在这里，如果可以的话，我也在寻找一种不使用多个数组（维度矩阵）的方法。

添加了文本文件，我不断收到[warning] passing arg 3 of dijkstra from incompatible pointer type

#include <stdio.h>
#define MAX 1000

void dijkstra(int n,int v,int cost[n][n],int dist[n]);

int main()
{
    int n,v, aux, aux1, aux2;

    int arc;
    FILE *archive;
    archive= fopen("TEXTFILE.txt","r");
    fscanf(archive,"%d %d",&n,&arc );
    printf("%d %d \n",n, arc);
    int dist[n];
    int k = 0;
    int rows = n;
    int cols = n;
    int i = 0;
    int j = 0;
    int **cost;
    cost = malloc(rows * sizeof(int));
    for (i = 0; i < rows; i++){
        cost[i] = malloc(cols * sizeof(int));
    }

    while (!feof(archive)){
        fscanf (archivo,"%d %d %d", &aux, &aux1, &aux2);
        cost[aux][aux1] = aux2;
        printf("%d %d %d\n", aux, aux1, cost[aux][aux1]);
        aux = 0 ;
        aux1 = 0;
        aux2 = 0;
    }

    printf("\n Enter the Source Node:");
    scanf("%d",&v);

    int h,u,count,w,flag[n],min;

    for(h=0;h < n;h++)
    {
        flag[h]=0;
        dist[h]=cost[v][h];
    }
    count=1;
    while(count&lt;n)
    {
        min=MAX;
        for(w=0;w < n;w++)
        {
            if(dist[w] < min && !flag[w])
            {
                min=dist[w];
                u=w;
            }
        }
        flag[u]=1;
        count++;
        for(w=0; w < n;w++)
        {
            if((dist[u] + cost[u][w] < dist[w]) && !flag[w])
            {
                dist[w] = dist[u] + cost[u][w];
            }
        }
    }

    printf("\n   Shortest Path from Node %d: ",v);
    printf("\n#################################\n\n");

    for(h=0;h < n;h++)
    {

        printf("Distance to Node:%d is %d\n",(h+1),dist[h]);
    }

    system ("PAUSE");
    return 0;

}

文本文件

10 16
1 2  2 
1 4  8
2 4  4
3 4  3
3 5  4
3 8  8
4 5  7
5 6  2
5 7  2
5 8  4
6 7  1
6 9  2
7 8  1
7 10 4
8 10 4
9 10 1

Answer 1

您的代码中的逻辑错误是您通过读取文件设置了成本矩阵的值。但其他值默认为零，因此您总是将 min 设为零。因此，它们之间没有路径的一对节点被认为是最短距离。您需要使这些成本无限，即一些非常大的价值。

for(i = 0;i < n;i++)  
for(j = 0;j < n;j++)  
{
    if(i!=j)
    {
        if(cost[i][j]==0)
        {
            cost[i][j] = INF;
        }
    }
}