dijkstra c++ 代码

Dijkstra算法是一种用于寻找图中两点之间最短路径的经典算法，常用于解决单源最短路径问题。在C++中实现Dijkstra算法通常会用到优先队列（如`std::priority_queue`）和邻接表数据结构。

这是一个简单的Dijkstra算法实现示例：

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

struct Edge {
    int to, weight;
};

using namespace std;

class Graph {
private:
    vector<vector<Edge>> adjList; // 邻接列表存储边

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

    pair<int, int> dijkstra(int start) {
        vector<int> dist(adjList.size(), INT_MAX);
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        dist[start] = 0;
        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 : adjList[u]) {
                int v = edge.to;
                int newDist = dist[u] + edge.weight;
                if (newDist < dist[v]) {
                    dist[v] = newDist;
                    pq.push({dist[v], v});
                }
            }
        }
        return {start, dist[start]};
    }
};

int main() {
    Graph graph;
    // 添加节点和边...
    auto [shortestPath, distance] = graph.dijkstra(0); // 从节点0开始找最短路径
    cout << "Shortest path from node 0 is: " << shortestPath << endl;
    cout << "Distance of the shortest path is: " << distance << endl;
    return 0;
}

在这个例子中，我们首先创建一个邻接列表表示图，并添加边。然后在dijkstra函数中，初始化距离数组、优先队列，接着循环直到队列为空，每次从队列中取出距离最小的未访问节点，更新其相邻节点的距离。最后返回起点到终点的最短路径和距离。