Dijkstra算法C

Question

我能夠編譯g ++中的代碼，但由於某種原因，當我運行該程序時，它在幾秒鐘後崩潰。

我也意識到這個任務是在C語言中設想的，但我對這種語言知之甚少，我不知道問題在哪裏。如果任何人都可以給我提示，那會很棒，但這不是什麼大問題。

我只是想知道哪裏出錯，因爲程序編譯沒有任何問題

這裏是代碼和主要功能是教授的測試代碼。

#include <cstdlib> 
#include <iostream> 
#include <stdio.h> 
using namespace std; 

struct listnode { 
struct listnode * next; 
int vertexnumber; 
}; 

struct listnode * shortest_path(int n, int s, int t, int * dist) { 

struct listnode * pathlist = NULL; 
    struct listnode * temp = NULL; 
    struct listnode * pathlisthead = NULL; 

    int i, j, k, S[9999], cost[9999], path[9999], p, min; 

    for (i = 0; i < n; i++) { 
     S[i] = 0; 
     cost[i] = 9999; 
    } 

    p = 0; 
    path[++p] = s; 
    pathlist = new struct listnode; 
    pathlisthead = pathlist; 
    pathlist->vertexnumber = s; 
    S[s] = 1; 
    cost[s] = 0; 
    for (i = 1; i < n - 1; i++) { 
     k = -1; 
     min = 9999; 
     for (j = 0; j < n; j++) { 
      if (cost[j] < min && S[j] != 1) { 
       min = cost[j]; 
       k = j; 
      } 
     } 
     if (*(dist + i*n + j) <= cost[k]) { 
      p = 1; 
      pathlist = pathlisthead; 
     } 
     path[++p] = k; 
     pathlist->next = new struct listnode; 
     pathlist = pathlist->next; 
     pathlist->vertexnumber = k; 
     struct listnode * tmp = pathlisthead; 
     while (tmp != NULL) { 
      tmp = tmp->next; 
     } 
     S[k] = 1; 
     for (j = 0; j < n; j++) 
      if (*(dist + i*n + j) != 9999 && cost[j] >= cost[k] + *(dist + i*n + j) && S[j] != 1) 
       cost[j] = cost[k] + *(dist + i*n + j); 
     if (k == t) 
      break; 
    } 
    return pathlisthead; 
} 

int main(void) 
{ int dist[1000][1000]; 
    int i,j; 
    struct listnode *tmp; 
    for(i=0; i< 1000; i++) 
    for(j =0; j< 1000; j++) 
    { if(i<500 && j<500) 
      dist[i][j] = 110 + ((i*i +j*j + 13*(i+j))%20); 
     else 
      dist[i][j] = 200 + ((i*i +j*j + 13*(i+j))%20); 
    } 


    for(i=0; i< 1000; i++) 
    dist[i][i]=0; 
    for(i=0; i< 100; i++) 
    { dist[i][2*i+1] = 15; dist[2*i+1][i] = 15; 
     dist[i][2*i+2] = 15; dist[2*i+2][i] = 15; 
    } 
    dist[0][128] = 100; dist[128][0]=100; 
    dist[128][500] = 1; dist[500][128]= 1; 
    for(i = 0; i< 100; i++) 
    { dist[300+ (7*i)%100][300+(7*i+7)%100] = 1; 
     dist[300+ (7*i+7)%100][300+(7*i)%100] = 1; 
     dist[300+i][450] = 2; dist[450][300+1] = 2; 
    } 
    for(i=502; i<900; i++) 
    { dist[450][i] = 3; dist[i][450]=3; 
    dist[500][i] = 2; dist[i][500]=2; 
    dist[501][i] = 10; dist [i][501] = 10; 
    } 
    dist [500][900] = 50; dist[900][500]=50; 
    dist [899][900] = 49; dist[899][900]=49; 
    dist [900][999] = 1; dist [999][900] = 1; 
    printf("constructed distance matrix for graph with 1000 vertices\n"); 
    tmp = shortest_path(1000, 0, 999, &(dist[0][0])); 
    printf("The shortest path from 0 to 999 uses the vertices\n"); 
    while(tmp != NULL) 
    { printf("%d, ", tmp->vertexnumber); 
     tmp = tmp->next; 
    } 
    printf("End test\n"); 
    exit(0); 
} 

教授說結果應顯示：用於圖形

構造距離矩陣具有1000個頂點

從0到999的最短路徑使用頂點

0，128，500 ，900,9999，End test

Answer 1

我可以看到至少有一個地方會導致它崩潰。當您在這裏創建一個新的listnode：

pathlist->next = new struct listnode; 
    pathlist = pathlist->next; 
    pathlist->vertexnumber = k; 

你不要在next指針初始化到NULL。所以，當你開始通過列表迭代位置：

struct listnode * tmp = pathlisthead; 
    while (tmp != NULL) { 
     tmp = tmp->next; 
    } 

pathlisthead開始了指向的pathlist初始值，其中有一個next指向新listnode你剛剛構建的，其中有一個next指向記憶中的隨機位置。

結果是while循環最終爆炸。

如果在main開始處的1000 x 1000陣列導致堆棧溢出，但這可能取決於您的系統設置，這也不會令我感到意外。