Dijkstra SDSP Algorithm

Question

I'm trying to implement Dijkstra Algorithm for Single Destination Shortest Path using Adjacency List and PQ as Min Heap. The output must show path of all vertices to destination vertex, if path exists, and if yes, the sum of it (shortest), if no, NO PATH. Link to entire code

Input Format:

• First line is number of vertices, n
• Second line onwards: (Vertices from 1 to n)
  • First column is vertex.
  • After, multiple pairs, <vertex, weight>
• test.txt

4
1 2 4 3 5 4 5
4 1 7 3 3
2 1 3 4 10 

According to GDB, it showed Segmentation fault found at extractMin function.

Program received signal SIGSEGV, Segmentation fault.
0x00401746 in extractMin ()

Client.c

Extracting input from the text.txt file and create a directed graph

FILE *fptr = fopen("test.txt", "r");
    if (fptr == NULL) exit(1);

    int n;
    if (fscanf(fptr, "%d", &n) == 1 && n > 0)
    {
        Graph *graph = createGraph(n);
        int c;
        while ((c = fgetc(fptr)) != EOF && c != '\n');
        char *line = NULL;      
        size_t len = 0;        

        while (getline(&line, &len, fptr) > 0)
        {
            char *cur = line;
            int ccs = 0;
            int v1;

            if (sscanf(cur, "%d%n", &v1, &ccs) == 1)
            {
                cur += ccs;
                int v2;
                int w;
                while (sscanf(cur, "%d %d%n", &v2, &w, &ccs) == 2)
                {
                    addEdge(graph, v1, v2, w);
                    cur += ccs;
                }

                fputc('\n', stdout);
            }

        }
        free(line);
        for (int i = 0; i < n; i++)
            dijkstra(graph, i);
    }

Server.c

struct MinHeapNode* extractMin(MinHeap* minHeap)
{
    if (isEmpty(minHeap))
        return NULL;
 
    struct MinHeapNode* root = minHeap->array[0];
    struct MinHeapNode* lastNode = minHeap->array[minHeap->size - 1];
    minHeap->array[0] = lastNode;
 
    minHeap->pos[root->v] = minHeap->size-1;
    minHeap->pos[lastNode->v] = 0;
 
    --minHeap->size;
    minHeapify(minHeap, 0);
 
    return root;
}
void dijkstra(Graph* graph, int dest)
{
    int v = graph->vertices;
    int distance[v]; 
    int pathFollow[1000]={0};
    int ind = 0;

    MinHeap* minHeap = createMinHeap(v);
 
    for (int i = 0; i < v; ++i)
    {
        distance[v] = INT_MAX;
        minHeap->array[v] = newMinHeapNode(v, distance[v]);
        minHeap->pos[v] = v;
    }
 
    minHeap->array[dest] = newMinHeapNode(dest, distance[dest]);
    minHeap->pos[dest] = dest;
    distance[dest] = 0;
    decreaseKey(minHeap, dest, distance[dest]);
 
    minHeap->size = v;

    while (!isEmpty(minHeap))
    {
        struct MinHeapNode* minHeapNode = extractMin(minHeap);
        int u = minHeapNode->v;
        AdjListNode* path = graph->array[u].head;
        while (path != NULL)
        {
            int v = path->vertex;
            if (isInMinHeap(minHeap, v) && distance[u] != INT_MAX &&
              path->weight + distance[u] < distance[v])
            {
                distance[v] = distance[u] + path->weight;
                if(pathFollow[ind-1] != u)
                    pathFollow[ind++]=u;
                decreaseKey(minHeap, v, distance[v]);
            }
            path = path->next;
        }
    }
    printArr(distance, v, pathFollow, dest);
}

void printArr(int dist[], int n, int pathFollow[], int dest)
{
    printf("%d", dest+1);
    int j = 0;
    if(dist[n-1]!=0 && dist[n-1] < 100000000) 
    {
        int k = j;
        printf(" %d", pathFollow[k]+1);
        while(pathFollow[j]!=0) 
        {
        printf(" %d", pathFollow[j++]);
        }
        printf(" %d %d\n",n, dist[n-1]);
    }
    else
    {
        printf("NO PATH\n");
    }
}

Answer 1

I'm not going to debug this entire program but here are a few errors:

1. You create

    Graph *graph = createGraph(n);
   

and are then accessing graph->array[src].head.

This is a problem since n is just the total number of vertices, in your case 4 but when that addEdge() is called with something like 4 1 7, that is a heap-buffer-overflow. You need to account for the 0-indexed arrays that you create.

2. Another overflow problem, this time of the stack buffer, would be at:

   int v = graph->vertices;
   int distance[v];
   

But then this is referred to as

distance[v] = INT_MAX;

again not considering the 0-indexed array. Also, that code seems suspect and should be distance[i] = INT_MAX I believe.

Please review your own code for more such errors, especially for array index overflows, use Address Sanitizers to check code for memory errors, step through each line of the program, and see if what's expected is indeed happening. You mention the program faults around extractMin(). Check if it is accessing the memory it is supposed to access. SIGSEGV indicates illegal memory access. Is struct MinHeapNode* root pointing to something you allocated? Is struct MinHeapNode* lastNode pointing to something you allocated?