优先队列解决旅行售货员问题c语言代码实现

以下是使用C语言实现优先队列解决旅行售货员问题的代码实现：

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

// 定义节点信息
typedef struct node {
    int id;  // 节点编号
    int dist;  // 距离起点的距离
    int visited;  // 节点是否被访问过
} Node;

// 定义优先队列结构体
typedef struct priority_queue {
    Node* heap;  // 存储节点的堆结构
    int size;  // 堆的大小
    int max_size;  // 堆的最大大小
} PriorityQueue;

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

// 将节点插入优先队列
void insert_node(PriorityQueue* queue, Node node) {
    int i;
    if (queue->size >= queue->max_size) {  // 队列已满
        return;
    }
    i = ++queue->size;
    while ((i > 1) && (queue->heap[i/2].dist > node.dist)) {  // 上滤操作
        queue->heap[i] = queue->heap[i/2];
        i /= 2;
    }
    queue->heap[i] = node;
}

// 弹出距离起点最近的节点
Node pop_node(PriorityQueue* queue) {
    int parent=1, child=2;
    Node min_node, last_node;
    if (queue->size == 0) {  // 队列为空
        return (Node){-1, -1, -1};
    }
    min_node = queue->heap[1];
    last_node = queue->heap[queue->size--];
    while (child <= queue->size) {  // 下滤操作
        if ((child < queue->size) && (queue->heap[child].dist > queue->heap[child+1].dist)) {
            child++;
        }
        if (last_node.dist > queue->heap[child].dist) {
            queue->heap[parent] = queue->heap[child];
        } else {
            break;
        }
        parent = child;
        child *= 2;
    }
    queue->heap[parent] = last_node;
    return min_node;
}

// 计算旅行售货员问题的近似解
void tsp(PriorityQueue* queue, int** graph, int n) {
    int i, j;
    Node node, next_node;
    int dist[n+1], path[n+1];
    for (i = 1; i <= n; i++) {
        dist[i] = INT_MAX;
        path[i] = -1;
    }
    dist[1] = 0;
    node.id = 1;
    node.dist = 0;
    node.visited = 0;
    insert_node(queue, node);
    while (queue->size > 0) {
        node = pop_node(queue);
        if (node.visited) {
            continue;
        }
        node.visited = 1;
        for (j = 1; j <= n; j++) {
            if ((graph[node.id][j] > 0) && (!queue->heap[j].visited)) {
                next_node.id = j;
                next_node.dist = node.dist + graph[node.id][j];
                if (next_node.dist < dist[j]) {
                    dist[j] = next_node.dist;
                    path[j] = node.id;
                    insert_node(queue, next_node);
                }
            }
        }
    }
    printf("起点：1\n终点：1\n路径：1");
    i = path[1];
    j = 2;
    while (i != 1) {
        printf("-%d", i);
        i = path[i];
        j++;
    }
    printf("-1\n路径长度：%d\n", dist[1]);
}

int main() {
    int n, i, j;
    int** graph;
    PriorityQueue* queue;
    printf("请输入节点数：\n");
    scanf("%d", &n);
    graph = (int**)malloc(sizeof(int*) * (n+1));
    for (i = 1; i <= n; i++) {
        graph[i] = (int*)malloc(sizeof(int) * (n+1));
        for (j = 1; j <= n; j++) {
            printf("请输入%d到%d的距离：\n", i, j);
            scanf("%d", &graph[i][j]);
        }
    }
    queue = init_priority_queue(n);
    tsp(queue, graph, n);
    return 0;
}

该代码使用优先队列来实现近似算法，使用了堆结构来存储节点信息，同时使用了邻接矩阵来存储节点间的距离信息。在计算过程中，使用了Dijkstra算法来计算距离起点最近的节点，并更新与该节点相邻的节点的距离信息。最终输出起点、终点、路径和路径长度等信息。需要注意的是，由于旅行售货员问题是NP难问题，因此使用优先队列解决只能得到近似解，而不能保证得到最优解。