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阵列导致堆栈溢出，但这可能取决于您的系统设置，这也不会令我感到意外。