dijkstra算法c++类模板实现

以下是Dijkstra算法的C++类模板实现，可以适用于任何具有权重边的图（有向或无向）：

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

template <typename T>
class Dijkstra {
private:
    std::vector<std::vector<std::pair<int, T>>> graph; // 存储图的邻接表
    std::vector<T> dist; // 存储每个顶点的最短距离
    std::vector<int> prev; // 存储每个顶点在最短路径中的前驱结点
    const T INF = std::numeric_limits<T>::max(); // 无穷大

public:
    Dijkstra(const std::vector<std::vector<std::pair<int, T>>>& g) : graph(g) {}

    void run(int start) {
        int n = graph.size();
        dist.assign(n, INF);
        prev.assign(n, -1);

        // 使用小根堆存储每个顶点的最短距离及其编号
        std::priority_queue<std::pair<T, int>, std::vector<std::pair<T, int>>, std::greater<>> pq;

        pq.emplace(0, start);
        dist[start] = 0;
        while (!pq.empty()) {
            auto [d, u] = pq.top();
            pq.pop();

            // 如果当前节点已经被处理过，就直接跳过
            if (dist[u] < d) {
                continue;
            }

            // 遍历当前节点所有的邻居节点
            for (auto [v, w] : graph[u]) {
                T newDist = dist[u] + w;
                if (newDist < dist[v]) {
                    dist[v] = newDist;
                    prev[v] = u;
                    pq.emplace(newDist, v);
                }
            }
        }
    }

    // 获取从起点到终点的最短距离
    T getDistance(int end) const {
        return dist[end];
    }

    // 获取从起点到终点的最短路径
    std::vector<int> getPath(int end) const {
        std::vector<int> path;
        for (int u = end; u != -1; u = prev[u]) {
            path.push_back(u);
        }
        std::reverse(path.begin(), path.end());
        return path;
    }
};

使用示例：

int main() {
    // 构建有向图
    int n = 5;
    std::vector<std::vector<std::pair<int, int>>> graph(n);
    graph[0].emplace_back(1, 10);
    graph[0].emplace_back(3, 5);
    graph[1].emplace_back(2, 1);
    graph[1].emplace_back(3, 2);
    graph[2].emplace_back(4, 4);
    graph[3].emplace_back(1, 3);
    graph[3].emplace_back(2, 9);
    graph[3].emplace_back(4, 2);

    // 运行Dijkstra算法
    Dijkstra<int> dijkstra(graph);
    dijkstra.run(0);

    // 输出结果
    for (int i = 0; i < n; i++) {
        std::cout << "Distance from 0 to " << i << ": " << dijkstra.getDistance(i) << std::endl;
        auto path = dijkstra.getPath(i);
        std::cout << "Path from 0 to " << i << ": ";
        for (int u : path) {
            std::cout << u << " ";
        }
        std::cout << std::endl;
    }

    return 0;
}

输出结果：

Distance from 0 to 0: 0
Path from 0 to 0: 0 
Distance from 0 to 1: 8
Path from 0 to 1: 0 3 1 
Distance from 0 to 2: 9
Path from 0 to 2: 0 3 1 2 
Distance from 0 to 3: 5
Path from 0 to 3: 0 3 
Distance from 0 to 4: 7
Path from 0 to 4: 0 3 4