Dijkstra's Algorithm in C

Question

I am able to compile the code in g++ but for some reason when I run the program, it crashes after a few seconds.

I also realized the assignment was suppose to b in C but I don't know much about that language and I don't know where the issues are. If anyone can give me tips on that it would be great but it isn't a big deal.

I just want to know where the error is since the program compiles without any issues

Here is the code and the main function is the professor's test code.

#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);
}

The professor said the result should show:

constructed distance matrix for graph with 1000 vertices

The shortest path from 0 to 999 uses the vertices

0, 128, 500, 900, 999, End test

Answer 1

I can see at least one place that will cause it to crash. When you create a new listnode here:

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

you don't initialise the next pointer to NULL. So when you start iterating through the list here:

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

pathlisthead starts off pointing to the initial value of pathlist, which has a next pointing to the new listnode you've just constructed, which has a next pointing to a random location in memory.

The result is that the while loop eventually explodes.

It also wouldn't surprise me if that 1000 x 1000 array at the start of main causes a stack overflow, but that may depend on your system settings.