Segmentation Core Dump Problem in Dijkstra Algorithm

Posted By: Anonymous

I tried to implement Dijkstra algorithm with adjacency list,the code is exhibiting strange behaviour when i remove the cout statement from updatePriority() function it throws segmentation core dumped error and if the cout statement is included it doesn’t throw any error, everything working fine.

what might be the cause for it ?

i have included my code below
thank you..

#include <iostream>

using namespace std;
struct Node
{
    int vertex;
    int edgeCost;
    struct Node *next;
};
struct Graph
{
    int numVertices;
    int *visited;
    int *distance;
    int *path;
    struct Node **adjLists;
};
struct PQueue
{
    int item;
    int priority;
    struct PQueue *next;
};
Node *createNode(int v)
{
    struct Node *node = (struct Node *)malloc(sizeof(struct Node));
    node->vertex = v;
    node->edgeCost = 0;
    node->next = NULL;
    return node;
}
Graph *createGraph(int vertices)
{
    struct Graph *graph = (struct Graph *)malloc(sizeof(struct Graph));
    graph->numVertices = vertices;

    graph->adjLists = (struct Node **)malloc(vertices * sizeof(struct node *));

    graph->visited = (int *)malloc(vertices * sizeof(int));
    graph->distance = (int *)malloc(vertices * sizeof(int));
    graph->path = (int *)malloc(vertices * sizeof(int));

    for (int i = 0; i < vertices; i++)
    {
        graph->adjLists[i] = NULL;
        graph->visited[i] = 0;
    }
    return graph;
}
void addEdge(struct Graph *graph, int src, int dest, int cost)
{
    struct Node *newNode = createNode(dest);
    newNode->edgeCost = cost;
    newNode->next = graph->adjLists[src];
    graph->adjLists[src] = newNode;

    newNode = createNode(src);
    newNode->edgeCost = cost;
    newNode->next = graph->adjLists[dest];
    graph->adjLists[dest] = newNode;
}

void printGraph(struct Graph *graph)
{
    int v;
    for (v = 0; v < graph->numVertices; v++)
    {
        struct Node *temp = graph->adjLists[v];
        printf("n Adjacency list of vertex %dn ", v);
        while (temp)
        {
            printf("%d -> ", temp->vertex);
            temp = temp->next;
        }
        printf("n");
    }
}
PQueue *createQueueNode(int item, int priority)
{
    struct PQueue *node = (struct PQueue *)malloc(sizeof(struct PQueue));
    node->item = item;
    node->priority = priority;
    node->next = NULL;
    return node;
}
void enqueue(struct PQueue **head, int item, int priority)
{
    struct PQueue *node = createQueueNode(item, priority);
    if (*head == NULL)
    {
        *head = node;
    }
    else
    {
        struct PQueue *temp = *head;
        if (priority <= temp->priority)
        {
            node->next = temp;
            *head = node;
        }
        else
        {
            struct PQueue *t;
            while (temp != NULL && priority < temp->priority)
            {
                t = temp;
                temp = temp->next;
            }
            t->next = node;
            node->next = temp;
        }
    }
}
PQueue *dequeue(struct PQueue **head)
{
    if (*head == NULL)
    {
        cout << "queue is empty";
        return NULL;
    }
    struct PQueue *temp = *head;
    *head = (*head)->next;
    return temp;
}
void printQueue(struct PQueue *head)
{
    struct PQueue *temp = head;
    while (temp != NULL)
    {
        cout << "item " << temp->item << " priority " << temp->priority << endl;
        temp = temp->next;
    }
    cout << "----------------------" << endl;
}
void updatePriority(struct PQueue **head, int item, int priority)
{
    struct PQueue *temp = *head;
    while (temp != NULL && temp->item != item)
    {
        // cout << temp->item;
        temp = temp->next;
    }
    if (temp == NULL)
    {
        enqueue(&(*head), item, priority);
    }
    else
    {
        temp->priority = priority;
    }
}
void Dijkstra(struct Graph *graph, int src)
{
    struct PQueue *head = createQueueNode(src, 0);
    int v, cost;
    for (int i = 0; i < graph->numVertices; i++)
    {
        graph->distance[i] = -1;
    }
    graph->distance[src] = 0;
    while (head != NULL)
    {
        v = dequeue(&head)->item;
        struct Node *temp = graph->adjLists[v];
        while (temp != NULL)
        {
            int newDistance = graph->distance[v] + temp->edgeCost;
            if (graph->distance[temp->vertex] == -1)
            {
                graph->distance[temp->vertex] = newDistance;
                updatePriority(&head, temp->vertex, newDistance);
            }
            else if (graph->distance[temp->vertex] > newDistance)
            {
                graph->distance[temp->vertex] = newDistance;
                updatePriority(&head, temp->vertex, newDistance);
            }
            temp = temp->next;
        }
    }
}
int main()
{
    struct Graph *graph = createGraph(7);

    addEdge(graph, 0, 2, 1);
    addEdge(graph, 0, 3, 2);
    addEdge(graph, 1, 2, 2);
    addEdge(graph, 2, 3, 1);
    addEdge(graph, 1, 5, 3);
    addEdge(graph, 2, 4, 3);
    addEdge(graph, 4, 5, 2);
    addEdge(graph, 3, 6, 1);
    addEdge(graph, 6, 5, 1);

    // printGraph(graph);

    Dijkstra(graph, 2);
    cout << endl;
    for (int i = 0; i < graph->numVertices; i++)
    {
        cout << "distance to " << i << " is " << graph->distance[i] << endl;
    }

    return 0;
}

Solution

There is an error in enqueue in this line:

while (temp != NULL && priority < temp->priority)

This condition will be false on the verify first evaluation, because of the preceding if condition which was false. By consequence, the variable t will remain uninitialised, and the following line will perform an uncontrolled dereferencing, potentially raising a segmentation fault:

t->next = node;

It can be confusing that adding a cout somewhere may determine whether the segmentation fault occurs or not… it all depends on what the actual (undefined) value is of t in the compiled code.

The correction is of course to change the while condition:

while (temp != NULL && priority > temp->priority)

Answered By: Anonymous

Disclaimer: This content is shared under creative common license cc-by-sa 3.0. It is generated from StackExchange Website Network.