Dijkstra算法

Question

我想在C中使用雙數組和內存分配來實現dijkstra算法（解決它ina大的大圖），但我不能讓它運行。我的代碼不會變成任何錯誤，只有所有的答案都是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

在你的代碼的邏輯錯誤是你從文件中讀取設置成本矩陣的值。但其他值默認爲零，所以你總是得到零分。因此，它們之間沒有路徑的一對節點被認爲是最短距離。你需要使這些成本無限大，即一些非常大的價值。

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