Dijkstra算法中的Segmentation Core Dump问题

Question

我尝试用邻接表实现 Dijkstra 算法，当我从 updatePriority() 函数中删除 cout 语句时，代码表现出奇怪的行为，它抛出分段核心转储错误，如果包含 cout 语句，它不会抛出任何错误，一切正常。

可能是什么原因造成的？

我在下面包含了我的代码谢谢..

#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 %d\n ", 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;
}

Answer 1

enqueue这一行有错误：

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

此条件在验证第一次评估时将为假，因为前面的 if 条件为假。因此，变量 t 将保持未初始化状态，并且以下行将执行不受控制的取消引用，可能会引发分段错误：

t->next = node;

在某处添加一个 cout 可能会让人感到困惑，这可能会决定是否发生分段错误......这完全取决于 t 中的实际（未定义）值是什么编译代码。

修正当然是改变while条件：

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

Dijkstra算法中的Segmentation Core Dump问题

Segmentation Core Dump Problem in Dijkstra Algorithm

c++

algorithm

graph

dijkstra

data-structures