c++实现dijsktra算法

### C++ 实现 Dijkstra 算法

Dijkstra 算法用于计算加权图中的最短路径。下面是一个完整的 C++ 实现，该实现基于优先队列来优化性能[^2]。

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

using namespace std;

struct Node {
    int vertex;
    int weight;
};

typedef pair<int, int> Pair; // {distance, vertex}

void addEdge(vector<vector<Node>>& adjList, int u, int v, int w) {
    adjList[u].push_back({v, w});
    adjList[v].push_back({u, w}); // 如果是无向图，则加上这一句
}

// 使用最小堆作为优先队列
class CompareDist {
public:
    bool operator()(const Pair& p1, const Pair& p2) {
        return p1.first > p2.first;
    }
};

vector<int> dijkstra(int V, vector<vector<Node>> adj[], int S) {
    priority_queue<Pair, vector<Pair>, CompareDist> pq;
    
    vector<int> dist(V, INT_MAX);
    dist[S] = 0;
    pq.push(make_pair(0, S));

    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();

        for (auto it : adj[u]) {
            int v = it.vertex;
            int weight = it.weight;

            if (dist[v] > dist[u] + weight) {
                dist[v] = dist[u] + weight;
                pq.push(make_pair(dist[v], v));
            }
        }
    }

    return dist;
}

此代码片段展示了如何使用邻接表表示图形结构并应用 Dijkstra 的算法找到源顶点到其他所有顶点之间的最短距离。通过引入 `priority_queue` 来提高效率，从而使得每次都能快速获取当前未处理节点中具有最小估计成本的一个。

对于更复杂的应用场景，可以考虑利用成熟的第三方库如 Boost Graph Library 提供的支持功能[^3]。