dijkstra算法C++

Dijkstra算法是一种用于解决单源最短路径问题的贪心算法，通常应用于图论中。在C++中实现Dijkstra算法，一般会采用优先队列（如`std::priority_queue`）来存储待处理的节点及其距离。以下是基本步骤：

1. 初始化：给起点赋予0的距离，其他所有节点的距离设为无穷大；将起点加入优先队列。

2. 主循环：从优先队列中取出当前距离最小的未访问节点u，并更新与其相邻的所有节点的距离。如果通过u可达的新距离更小，则更新新距离并把节点添加回优先队列。

3. 结束条件：当优先队列为空或当前节点已经是终点时，算法结束。此时，已知的最短路径就是从起点到终点的路径。

以下是一个简单的C++ Dijkstra算法实现示例：

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

struct Edge {
    int to, weight;
};

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

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

    std::pair<int, std::vector<int>> dijkstra(int start) {
        std::vector<int> dist(adj.size(), std::numeric_limits<int>::max());
        dist[start] = 0;

        std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<std::pair<int, int>>> pq;
        pq.push({0, start});

        while (!pq.empty()) {
            int u = pq.top().second;
            pq.pop();
            for (const auto &edge : adj[u]) {
                int new_dist = dist[u] + edge.weight;
                if (new_dist < dist[edge.to]) {
                    dist[edge.to] = new_dist;
                    pq.push({dist[edge.to], edge.to});
                }
            }
        }

        return {dist[end], getShortestPath(dist, start)};
    }

private:
    std::vector<int> getShortestPath(std::vector<int>& dist, int start) {
        std::vector<int> path;
        int current = end;
        while (current != start) {
            path.push_back(current);
            for (int neighbor : adj[current]) {
                if (dist[neighbor] == dist[current] - neighbor_weight(neighbor)) {
                    current = neighbor;
                    break;
                }
            }
        }
        path.push_back(start); // 添加起点
        std::reverse(path.begin(), path.end()); // 逆序路径
        return path;
    }
};

在这个例子中，`Graph`类包含邻接列表表示图，`dijkstra`函数负责执行Dijkstra算法，返回最短路径的距离和实际路径。