Skip to content
Fix Code Error

Segmentation Core Dump Problem in Dijkstra Algorithm

June 29, 2021 by Code Error
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

Related Articles

  • Combining items using XSLT Transform
  • What are the new features in C++17?
  • Java - Find shortest path between 2 points in a distance…
  • no match for ‘operator
  • Getting weird compilation error in defining a std::set with…
  • sql query to find priority jobs
  • How to generate JAXB classes from XSD?
  • I do not use TBB, but I get linker errors related to TBB
  • 3D Rotation of a camera using its own, new axes
  • How to create ranges and synonym constants in C#?

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

Post navigation

Previous Post:

Comparing content of 2 files with md5sum

Next Post:

How to initialize `LocalizationResourceManager`

Leave a Reply Cancel reply

Your email address will not be published. Required fields are marked *

  • Get code errors & solutions at akashmittal.com
© 2022 Fix Code Error