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

以下是基于优先队列式分支限界法的Dijkstra算法的完整C语言代码：

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

#define MAXV 1000  // 最大顶点数
#define INF INT_MAX  // 无穷大

typedef struct {
    int v;  // 边的目标顶点
    int w;  // 边的权值
} Edge;

typedef struct {
    Edge **edges;  // 指向边的指针数组
    int degree;  // 顶点的度
    int d;  // 到源点的距离
    int parent;  // 前驱结点
    int visited;  // 是否被访问过
} Vertex;

typedef struct {
    Vertex *vertices[MAXV];  // 指向顶点的指针数组
    int nvertices;  // 顶点数
    int nedges;  // 边数
} Graph;

// 创建一条边
Edge *create_edge(int v, int w) {
    Edge *edge = (Edge *)malloc(sizeof(Edge));
    edge->v = v;
    edge->w = w;
    return edge;
}

// 创建一个顶点
Vertex *create_vertex() {
    Vertex *vertex = (Vertex *)malloc(sizeof(Vertex));
    vertex->edges = (Edge **)malloc(sizeof(Edge *) * MAXV);
    vertex->degree = 0;
    vertex->d = INF;
    vertex->parent = -1;
    vertex->visited = 0;
    return vertex;
}

// 向图中添加一条边
void add_edge(Graph *graph, int u, int v, int w) {
    Edge *edge = create_edge(v, w);
    graph->vertices[u]->edges[graph->vertices[u]->degree++] = edge;
    graph->nedges++;
}

// 创建一个图
Graph *create_graph(int nvertices) {
    Graph *graph = (Graph *)malloc(sizeof(Graph));
    graph->nvertices = nvertices;
    graph->nedges = 0;
    for (int i = 0; i < nvertices; i++) {
        graph->vertices[i] = create_vertex();
    }
    return graph;
}

// 释放图的内存
void free_graph(Graph *graph) {
    for (int i = 0; i < graph->nvertices; i++) {
        Vertex *vertex = graph->vertices[i];
        for (int j = 0; j < vertex->degree; j++) {
            free(vertex->edges[j]);
        }
        free(vertex->edges);
        free(vertex);
    }
    free(graph);
}

// 优先队列
typedef struct {
    int v;  // 顶点
    int d;  // 到源点的距离
} PQItem;

typedef struct {
    PQItem items[MAXV];
    int size;  // 队列中元素个数
} PriorityQueue;

// 创建一个优先队列
PriorityQueue *create_priority_queue() {
    PriorityQueue *pq = (PriorityQueue *)malloc(sizeof(PriorityQueue));
    pq->size = 0;
    return pq;
}

// 入队
void enqueue(PriorityQueue *pq, int v, int d) {
    PQItem item = {v, d};
    int i = pq->size++;
    while (i > 0) {
        int p = (i - 1) / 2;
        if (pq->items[p].d <= item.d) {
            break;
        }
        pq->items[i] = pq->items[p];
        i = p;
    }
    pq->items[i] = item;
}

// 出队
PQItem dequeue(PriorityQueue *pq) {
    PQItem item = pq->items[0];
    pq->size--;
    PQItem last = pq->items[pq->size];
    int i = 0;
    while (i * 2 + 1 < pq->size) {
        int left = i * 2 + 1;
        int right = i * 2 + 2;
        int child = right < pq->size && pq->items[right].d < pq->items[left].d ? right : left;
        if (last.d <= pq->items[child].d) {
            break;
        }
        pq->items[i] = pq->items[child];
        i = child;
    }
    pq->items[i] = last;
    return item;
}

// 判断队列是否为空
int is_empty(PriorityQueue *pq) {
    return pq->size == 0;
}

// Dijkstra算法
void dijkstra(Graph *graph, int s) {
    graph->vertices[s]->d = 0;
    PriorityQueue *pq = create_priority_queue();
    enqueue(pq, s, 0);
    while (!is_empty(pq)) {
        PQItem item = dequeue(pq);
        int u = item.v;
        if (graph->vertices[u]->visited) {
            continue;
        }
        graph->vertices[u]->visited = 1;
        for (int i = 0; i < graph->vertices[u]->degree; i++) {
            Edge *edge = graph->vertices[u]->edges[i];
            int v = edge->v;
            int w = edge->w;
            if (graph->vertices[v]->d > graph->vertices[u]->d + w) {
                graph->vertices[v]->d = graph->vertices[u]->d + w;
                graph->vertices[v]->parent = u;
                enqueue(pq, v, graph->vertices[v]->d);
            }
        }
    }
    free(pq);
}

// 打印最短路径
void print_path(Graph *graph, int s, int v) {
    if (v == s) {
        printf("%d ", s);
    } else if (graph->vertices[v]->parent == -1) {
        printf("不存在从%d到%d的路径\n", s, v);
    } else {
        print_path(graph, s, graph->vertices[v]->parent);
        printf("%d ", v);
    }
}

int main() {
    Graph *graph = create_graph(6);
    add_edge(graph, 0, 1, 10);
    add_edge(graph, 0, 2, 5);
    add_edge(graph, 1, 2, 2);
    add_edge(graph, 1, 3, 1);
    add_edge(graph, 2, 1, 3);
    add_edge(graph, 2, 3, 9);
    add_edge(graph, 2, 4, 2);
    add_edge(graph, 3, 4, 4);
    add_edge(graph, 4, 3, 6);
    add_edge(graph, 4, 0, 7);
    add_edge(graph, 4, 5, 1);
    add_edge(graph, 5, 0, 3);
    add_edge(graph, 5, 2, 2);
    dijkstra(graph, 0);
    for (int i = 0; i < graph->nvertices; i++) {
        printf("到%d的最短路径是: ", i);
        print_path(graph, 0, i);
        printf("，距离为%d\n", graph->vertices[i]->d);
    }
    free_graph(graph);
    return 0;
}

该代码实现了一个简单的图，其中顶点0到顶点5的最短路径以及距离。你可以根据需要修改顶点数、边数和边的权值等参数。