帮我编辑一个优先队列式分支限界法求解单源最短路径的c++代码
时间: 2024-02-26 22:27:19 浏览: 21
好的,以下是一个基于优先队列式分支限界法的Dijkstra算法求解单源最短路径的C代码:
```
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define MAX_VERTEX_NUM 100 // 最大顶点数
typedef struct {
int edges[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵
int vertex_num; // 顶点数
} Graph;
typedef struct {
int vertex; // 顶点
int weight; // 权重
} Node;
typedef struct {
Node *data; // 数据
int size; // 当前元素个数
int capacity; // 队列容量
} PriorityQueue;
// 初始化优先队列
PriorityQueue *init_priority_queue(int capacity) {
PriorityQueue *queue = (PriorityQueue *)malloc(sizeof(PriorityQueue));
queue->data = (Node *)malloc(sizeof(Node) * (capacity + 1)); // 从下标1开始存储元素
queue->size = 0;
queue->capacity = capacity;
return queue;
}
// 入队
void enqueue(PriorityQueue *queue, Node node) {
int i;
if (queue->size >= queue->capacity) {
return; // 队列已满
}
// 找到插入位置
for (i = queue->size; i > 0 && queue->data[i / 2].weight > node.weight; i /= 2) {
queue->data[i] = queue->data[i / 2];
}
queue->data[i] = node;
queue->size++;
}
// 出队
Node dequeue(PriorityQueue *queue) {
int i, child;
Node min_node, last_node;
if (queue->size == 0) {
min_node.vertex = -1;
min_node.weight = -1;
return min_node; // 队列为空
}
min_node = queue->data[1];
last_node = queue->data[queue->size--];
// 从上往下调整堆
for (i = 1; i * 2 <= queue->size; i = child) {
child = i * 2;
if (child != queue->size && queue->data[child + 1].weight < queue->data[child].weight) {
child++; // 取左右子节点中较小的一个
}
if (last_node.weight > queue->data[child].weight) {
queue->data[i] = queue->data[child];
} else {
break;
}
}
queue->data[i] = last_node;
return min_node;
}
// Dijkstra算法
void dijkstra(Graph *graph, int start_vertex, int *dist, int *prev) {
int i, j;
Node node;
PriorityQueue *queue = init_priority_queue(graph->vertex_num); // 初始化优先队列
for (i = 0; i < graph->vertex_num; i++) {
dist[i] = INT_MAX; // 到所有顶点的距离初始化为无穷大
prev[i] = -1; // 前驱顶点初始化为-1
}
dist[start_vertex] = 0; // 起点到自身的距离为0
node.vertex = start_vertex;
node.weight = 0;
enqueue(queue, node); // 将起点加入优先队列
while (queue->size > 0) {
node = dequeue(queue); // 取出当前距离最小的顶点
if (node.vertex == -1) {
break; // 所有顶点都已遍历完
}
// 对当前顶点的所有邻接点进行松弛操作
for (j = 0; j < graph->vertex_num; j++) {
if (graph->edges[node.vertex][j] != -1 && dist[node.vertex] + graph->edges[node.vertex][j] < dist[j]) {
dist[j] = dist[node.vertex] + graph->edges[node.vertex][j];
prev[j] = node.vertex;
// 将松弛后的顶点加入优先队列
node.vertex = j;
node.weight = dist[j];
enqueue(queue, node);
}
}
}
free(queue->data);
free(queue);
}
int main() {
int i, j;
Graph graph;
int dist[MAX_VERTEX_NUM], prev[MAX_VERTEX_NUM];
printf("请输入顶点数:");
scanf("%d", &graph.vertex_num);
// 初始化邻接矩阵
for (i = 0; i < graph.vertex_num; i++) {
for (j = 0; j < graph.vertex_num; j++) {
graph.edges[i][j] = -1;
}
}
// 输入边信息
printf("请输入边数:");
int edge_num;
scanf("%d", &edge_num);
printf("请输入边的起点、终点、距离:\n");
int start_vertex, end_vertex, weight;
for (i = 0; i < edge_num; i++) {
scanf("%d %d %d", &start_vertex, &end_vertex, &weight);
graph.edges[start_vertex][end_vertex] = weight;
}
printf("请输入起点:");
scanf("%d", &start_vertex);
dijkstra(&graph, start_vertex, dist, prev);
printf("各顶点到起点的最短路径长度:\n");
for (i = 0; i < graph.vertex_num; i++) {
printf("%d ", dist[i]);
}
printf("\n各顶点的前驱顶点:\n");
for (i = 0; i < graph.vertex_num; i++) {
printf("%d ", prev[i]);
}
printf("\n");
return 0;
}
```
这段代码使用了优先队列来维护当前未确定最短路径的顶点,每次从队列中取出距离起点最近的顶点进行松弛操作,并将松弛后的顶点加入队列。如果队列为空,则表示所有顶点都已确定最短路径。