采用优先队列式分支限界法编程实现单源最短路径问题解决算法实验感想

单源最短路径问题是图论中的一个经典问题，对于算法的学习和理解有很大的帮助。在实验中，采用优先队列式分支限界法对单源最短路径问题进行求解，可以更好地理解这个问题和算法的本质。

通过实验，我深刻体会到了优先队列式分支限界法的优点：可以有效地降低时间复杂度，提高算法的效率。同时，在实现过程中，我也遇到了一些困难，例如如何设计数据结构、如何确定搜索顺序等，但通过不断的尝试和调试，最终成功地实现了算法。

除此之外，我还发现，对于单源最短路径问题，不同的算法有不同的适用场景和优缺点，需要根据具体情况进行选择和使用。因此，学习算法不仅要关注算法本身，还需要了解其应用场景和特点，才能更好地解决实际问题。

相关问题

采用优先队列式分支限界法编程实现单源最短路径问题解决算法完整代码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的最短路径以及距离。你可以根据需要修改顶点数、边数和边的权值等参数。

采用优先队列式分支限界法编程实现单源最短路径问题解决算法完整代码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;
}