dijkstra优先队列优化c++代码

Dijkstra算法是一种用于寻找图中两点之间最短路径的经典算法，通常会利用优先队列（如二叉堆）来优化搜索过程。在C++中，我们可以使用`std::priority_queue`来实现这个数据结构。下面是一个简化版的Dijkstra算法使用优先队列的示例：

#include <iostream>
#include <vector>
#include <queue>
#include <limits>

struct Node {
    int id;
    int dist;
    bool visited;

    Node(int _id, int _dist) : id(_id), dist(_dist), visited(false) {}
    bool operator<(const Node& other) const { return dist < other.dist; }
};

void dijkstra(std::vector<std::pair<int, int>>& graph, int start) {
    std::priority_queue<Node> pq;
    std::vector<int> dist(graph.size(), std::numeric_limits<int>::max());
    dist[start] = 0;
    pq.push(Node(start, 0));

    while (!pq.empty()) {
        Node current = pq.top();
        pq.pop();

        if (current.visited)
            continue;

        current.visited = true;

        for (auto [neighbor, weight] : graph[current.id]) {
            int new_dist = current.dist + weight;
            if (new_dist < dist[neighbor]) {
                dist[neighbor] = new_dist;
                pq.push(Node(neighbor, new_dist));
            }
        }
    }

    // 打印结果
    for (int i = 0; i < graph.size(); ++i) {
        if (dist[i] != std::numeric_limits<int>::max())
            std::cout << "Node " << i << ": Shortest distance from start is " << dist[i] << std::endl;
    }
}

// 使用示例
int main() {
    std::vector<std::pair<int, int>> graph = {{0, 4}, {1, 2}, {2, 7}, {3, 9}, {3, 14}, {4, 10}, {5, 1}, {6, 2}};
    dijkstra(graph, 0);
    return 0;
}

在这个例子中，我们首先创建一个`Node`结构体表示图中的每个节点，包含ID、距离值和访问标志。然后，我们使用`std::priority_queue`存储待处理的节点，并按照距离值排序。在每次循环中，我们会选择距离最近未访问过的节点，并更新其相邻节点的距离。