Алгоритм Dijkstra

Question

Я пытаюсь реализовать алгоритм dijkstra в C, используя двойные массивы с распределением памяти (чтобы решить его в большом большом графике), но я не могу запустить его. Мой код не превращает никакой ошибки, только то, что все ответы равны 0. Вот он, если вы можете также искать способ сделать это, не используя несколько массивов (матрица размеров).

ADDED TEXTFILE, я продолжаю получать [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; 

} 

Textfile

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 как ноль. Таким образом, пара узлов, не имеющих пути между ними, рассматривается как кратчайшее расстояние. Вам нужно сделать эти затраты INFINITE, т. Е. Некоторые очень большие значения.

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