Dijkstra算法中的分割核心转储问题

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 %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;
}

Answer 1

此行的enqueue中存在错误：

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

由于前面的if条件为false，因此在验证第一次评估时，此条件将为false。因此，变量t将保持未初始化状态，下面的行将执行不受控制的去引用，可能引发分段故障：

t->next = node;

在某个地方添加cout可能会决定分割故障是否发生，这可能会令人困惑。。。这完全取决于编译代码中CCD_ 5的实际(未定义(值。

校正当然是为了改变while条件：

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