采用优先队列式分支限界法编程实现单源最短路径问题解决算法完整代码C语言从a点到d点

以下是使用Dijkstra算法的优先队列式分支限界法的完整代码，实现单源最短路径问题的解决。其中，a点为起点，d点为终点。

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAX_VERTEX_NUM 100  // 顶点数的最大值
#define INFINITY 0x7FFFFFFF // 表示无穷大

// 边的定义
typedef struct EdgeNode {
    int adjvex;             // 邻接点编号
    int weight;             // 权值
    struct EdgeNode *next;  // 指向下一条边的指针
} EdgeNode;

// 顶点的定义
typedef struct VertexNode {
    int data;               // 顶点信息
    EdgeNode *first_edge;   // 边表头指针
} VertexNode;

VertexNode G[MAX_VERTEX_NUM];   // 图的邻接表表示
int dist[MAX_VERTEX_NUM];       // 存储起点到各点的最短距离
bool visited[MAX_VERTEX_NUM];   // 标记顶点是否已被访问
int path[MAX_VERTEX_NUM];       // 存储最短路径的前驱顶点

// 定义优先队列中的元素类型
typedef struct {
    int vertex;     // 顶点编号
    int priority;   // 优先级（即起点到该顶点的距离）
} QueueElemType;

// 定义优先队列
typedef struct {
    QueueElemType *heap;    // 存储队列元素的数组
    int size;               // 当前队列中元素的个数
    int capacity;           // 队列的容量（即数组的大小）
} PriorityQueue;

// 初始化优先队列
PriorityQueue *initPriorityQueue(int capacity) {
    PriorityQueue *queue = (PriorityQueue *)malloc(sizeof(PriorityQueue));
    queue->heap = (QueueElemType *)malloc(sizeof(QueueElemType) * (capacity + 1));
    queue->size = 0;
    queue->capacity = capacity;
    return queue;
}

// 销毁优先队列
void destroyPriorityQueue(PriorityQueue *queue) {
    free(queue->heap);
    free(queue);
}

// 向优先队列中插入一个元素
void enqueue(PriorityQueue *queue, QueueElemType elem) {
    if (queue->size == queue->capacity) {
        return; // 队列已满，不能再插入元素
    }
    int i = ++queue->size;
    while (i > 1 && queue->heap[i/2].priority > elem.priority) {
        queue->heap[i] = queue->heap[i/2];
        i /= 2;
    }
    queue->heap[i] = elem;
}

// 从优先队列中取出一个元素
QueueElemType dequeue(PriorityQueue *queue) {
    if (queue->size == 0) {
        QueueElemType empty = {0, 0};
        return empty; // 队列为空，返回一个空元素
    }
    QueueElemType min_elem = queue->heap[1];
    QueueElemType last_elem = queue->heap[queue->size--];
    int i = 1, child = 2;
    while (child <= queue->size) {
        if (child < queue->size && queue->heap[child+1].priority < queue->heap[child].priority) {
            child++;
        }
        if (last_elem.priority > queue->heap[child].priority) {
            queue->heap[i] = queue->heap[child];
        } else {
            break;
        }
        i = child;
        child *= 2;
    }
    queue->heap[i] = last_elem;
    return min_elem;
}

// Dijkstra算法
void Dijkstra(int a, int d) {
    // 初始化
    for (int i = 0; i < MAX_VERTEX_NUM; i++) {
        dist[i] = INFINITY;
        visited[i] = false;
        path[i] = -1;
    }
    dist[a] = 0;
    visited[a] = true;
    QueueElemType a_elem = {a, 0};
    PriorityQueue *queue = initPriorityQueue(MAX_VERTEX_NUM);
    enqueue(queue, a_elem);

    // 主循环
    while (queue->size > 0) {
        QueueElemType elem = dequeue(queue);
        int v = elem.vertex;
        visited[v] = true;
        EdgeNode *p = G[v].first_edge;
        while (p != NULL) {
            int w = p->adjvex;
            if (!visited[w]) {
                int new_dist = dist[v] + p->weight;
                if (new_dist < dist[w]) {
                    dist[w] = new_dist;
                    path[w] = v;
                    QueueElemType w_elem = {w, new_dist};
                    enqueue(queue, w_elem);
                }
            }
            p = p->next;
        }
    }

    // 输出结果
    printf("从%d到%d的最短路径长度为%d，路径为：", a, d, dist[d]);
    int p = d;
    while (p != -1) {
        printf("%d ", p);
        p = path[p];
    }
    printf("\n");

    // 释放内存
    destroyPriorityQueue(queue);
}

int main() {
    // 构造图
    EdgeNode *p;
    G[0].data = 0;
    G[1].data = 1;
    G[2].data = 2;
    G[3].data = 3;
    G[0].first_edge = p = (EdgeNode *)malloc(sizeof(EdgeNode));
    p->adjvex = 1;
    p->weight = 10;
    p->next = (EdgeNode *)malloc(sizeof(EdgeNode));
    p = p->next;
    p->adjvex = 3;
    p->weight = 30;
    p->next = NULL;
    G[1].first_edge = p = (EdgeNode *)malloc(sizeof(EdgeNode));
    p->adjvex = 2;
    p->weight = 50;
    p->next = NULL;
    G[2].first_edge = p = (EdgeNode *)malloc(sizeof(EdgeNode));
    p->adjvex = 3;
    p->weight = 10;
    p->next = NULL;
    G[3].first_edge = NULL;

    // 调用Dijkstra算法
    Dijkstra(0, 3);

    return 0;
}