狄克斯特拉算法c++实现

狄克斯特拉(Dijkstra's Algorithm)是一种用于求解单源最短路径问题的贪心算法。在C++中，它通常用于图论中寻找两个节点之间的最短路径。以下是简单的C++代码实现：

#include <vector>
#include <queue>
#include <limits.h>

using namespace std;

struct Edge {
    int to, weight;
};

class Graph {
private:
    vector<vector<Edge>> adj; // 邻接表表示图

public:
    void addEdge(int src, int dest, int weight) {
        adj[src].push_back({dest, weight});
    }

    pair<int, int> dijkstra(int start) {
        vector<int> dist(adj.size(), INT_MAX);
        dist[start] = 0;
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        pq.push({0, start});

        while (!pq.empty()) {
            int u = pq.top().second;
            pq.pop();
            if (dist[u] < pq.top().first) continue; // 更新路径优先级

            for (const auto &edge : adj[u]) {
                int v = edge.to;
                int newWeight = dist[u] + edge.weight;

                if (newWeight < dist[v]) {
                    dist[v] = newWeight;
                    pq.push({dist[v], v}); // 更新距离并重新入队
                }
            }
        }

        return {start, dist[end]};
    }
};

int main() {
    Graph g;
    // 添加边和顶点...
    int source = ...;
    auto [shortestDistance, end] = g.dijkstra(source);
    cout << "Shortest distance from node " << source << " is: " << shortestDistance << endl;
    cout << "Destination node: " << end << endl;
    return 0;
}