dijkstra堆优化算法c++

Dijkstra算法是一种用于解决单源最短路径问题的经典算法，它可以找到从一个起点到其他所有节点的最短路径。Dijkstra堆优化算法是对Dijkstra算法的一种优化，通过使用堆数据结构来提高算法的效率。

在C++中实现Dijkstra堆优化算法，可以按照以下步骤进行：

1. 创建一个图数据结构，于表示节点和边的关系。可以使用邻接表或邻接矩阵来表示图。

2. 初始化距离数组和堆数据结构。距离数组用于记录起点到每个节点的最短距离，初始值为无穷大。堆数据结构用于存储待处理的节点，并按照距离值进行排序。

3. 将起点加入堆中，并将其距离值设为0。

4. 重复以下步骤，直到堆为空：
- 从堆中取出距离值最小的节点。
- 遍历该节点的所有邻居节点：
- 如果通过当前节点到达邻居节点的距离小于邻居节点的当前最短距离，则更新邻居节点的最短距离，并将其加入堆中。

5. 最终得到起点到所有节点的最短距离。

下面是一个简单的C++代码示例，实现了Dijkstra堆优化算法：

#include <iostream>
#include <vector>
#include <queue>
#include <climits>

using namespace std;

typedef pair<int, int> pii;

void dijkstra(vector<vector<pii>>& graph, int start, vector<int>& dist) {
    int n = graph.size();
    dist.assign(n, INT_MAX);
    dist[start] = 0;
    
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    pq.push({0, start});
    
    while (!pq.empty()) {
        int u = pq.top().second;
        int d = pq.top().first;
        pq.pop();
        
        if (d > dist[u]) {
            continue;
        }
        
        for (auto& neighbor : graph[u]) {
            int v = neighbor.first;
            int w = neighbor.second;
            
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
}

int main() {
    int n = 5; // 节点数
    vector<vector<pii>> graph(n);
    
    // 添加边
    graph[0].push_back({1, 10});
    graph[0].push_back({4, 5});
    graph[1].push_back({2, 1});
    graph[1].push_back({4, 2});
    graph[2].push_back({3, 4});
    graph[3].push_back({2, 6});
    graph[3].push_back({0, 7});
    graph[4].push_back({1, 3});
    graph[4].push_back({2, 9});
    graph[4].push_back({3, 2});
    
    int start = 0; // 起点
    
    vector<int> dist;
    dijkstra(graph, start, dist);
    
    // 输出最短距离
    for (int i = 0; i < n; i++) {
        cout << "Distance from " << start << " to " << i << ": " << dist[i] << endl;
    }
    
    return 0;
}

这段代码实现了一个简单的有向图，使用邻接表来表示图的结构。通过调用`dijkstra`函数，可以计算出从起点到其他节点的最短距离，并将结果存储在`dist`数组中。