c++最短路优先队列

### C++ 中基于优先队列实现最短路径算法 在图结构中，Dijkstra 算法是一种常用的单源最短路径算法。为了提高效率，通常会利用优先队列来加速 Dijkstra 的执行过程。以下是通过优先队列实现 Dijkstra 算法的一个典型例子。 #### 使用 STL `priority_queue` 实现 Dijkstra 算法 C++ 提供了标准模板库中的 `std::priority_queue` 容器适配器，它能够高效地管理具有动态权重的顶点集合[^1]。下面展示了一个完整的代码示例： ```cpp #include <iostream> #include <vector> #include <queue> #include <climits> using namespace std; struct Node { int vertex; long weight; bool operator<(const Node& other) const { // 重载小于号以便 priority_queue 能够按权重排序 return this->weight > other.weight; // 注意这里是大根堆，默认需要反转逻辑 } }; void dijkstra(int start, vector<vector<pair<int, long>>>& graph, vector<long>& distances) { priority_queue<Node> pq; pq.push({start, 0}); distances[start] = 0; while (!pq.empty()) { Node current = pq.top(); pq.pop(); int u = current.vertex; long dist_u = current.weight; if (dist_u > distances[u]) continue; // 如果当前距离不是最优，则跳过 for (auto neighbor : graph[u]) { int v = neighbor.first; long weight_uv = neighbor.second; if (distances[v] > distances[u] + weight_uv) { distances[v] = distances[u] + weight_uv; pq.push({v, distances[v]}); } } } } int main() { int n = 5; // 假设有 5 个节点 vector<vector<pair<int, long>>> graph(n); // 构建加权无向图 graph[0].push_back({1, 10}); graph[0].push_back({4, 3}); graph[1].push_back({2, 1}); graph[2].push_back({3, 4}); graph[4].push_back({1, 1}); graph[4].push_back({2, 9}); vector<long> distances(n, LONG_MAX); dijkstra(0, graph, distances); // 从起点 0 开始计算最短路径 cout << "Shortest paths from node 0:" << endl; for (int i = 0; i < n; ++i) { cout << "Node " << i << ": " << distances[i] << endl; } return 0; } ``` 上述代码展示了如何使用优先队列优化 Dijkstra 算法的过程。其中的关键在于定义了一个自定义数据结构 `Node` 并实现了 `<` 运算符重载，从而让 `std::priority_queue` 可以按照权重从小到大的顺序弹出元素。 #### Boost Graph Library 的应用 除了手动编写 Dijkstra 算法外，还可以借助第三方库如 Boost.Graph 来简化开发流程。Boost.Graph 库内置支持多种图算法，其中包括基于优先队列优化的 Dijkstra 算法实现[^2]。以下是一个简单的调用方式： ```cpp #include <boost/graph/adjacency_list.hpp> #include <boost/graph/dijkstra_shortest_paths.hpp> typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, boost::no_property, boost::property<boost::edge_weight_t, int>> Graph; int main() { Graph g; typedef graph_traits<Graph>::vertex_descriptor Vertex; // 添加边并设置权重 Vertex s = add_vertex(g), t = add_vertex(g); add_edge(s, t, 10, g); property_map<Graph, boost::vertex_distance_t>::type distance_map; dijkstra_shortest_paths(g, s, distance_map); cout << "Distance to target: " << distance_map[t] << endl; return 0; } ``` 此方法无需自行维护优先队列，而是依赖于 Boost.Graph 内部的高度优化实现。 ---