dijkstra算法c++类模板实现

好的，下面是Dijkstra算法的C++类模板实现：

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

using namespace std;

template<typename T>
class Dijkstra {
private:
    vector<vector<pair<int, T>>> graph;
    vector<T> dist;
    vector<int> prev;
    int size;
public:
    Dijkstra(int n) {
        size = n;
        graph.resize(n);
        dist.resize(n, numeric_limits<T>::max());
        prev.resize(n, -1);
    }

    void addEdge(int from, int to, T weight) {
        graph[from].push_back(make_pair(to, weight));
    }

    void shortestPath(int start) {
        dist[start] = 0;
        priority_queue<pair<T, int>, vector<pair<T, int>>, greater<pair<T, int>>> pq;
        pq.push(make_pair(0, start));
        while (!pq.empty()) {
            auto curr = pq.top();
            pq.pop();
            int u = curr.second;
            T d = curr.first;
            if (d > dist[u]) continue;
            for (auto edge : graph[u]) {
                int v = edge.first;
                T w = edge.second;
                if (dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    prev[v] = u;
                    pq.push(make_pair(dist[v], v));
                }
            }
        }
    }

    T getDistance(int end) {
        return dist[end];
    }

    vector<int> getPath(int end) {
        vector<int> path;
        while (end != -1) {
            path.push_back(end);
            end = prev[end];
        }
        reverse(path.begin(), path.end());
        return path;
    }
};

使用方法如下：

int main() {
    // 创建一个5个节点的图
    Dijkstra<int> dijkstra(5);

    // 添加边和权重
    dijkstra.addEdge(0, 1, 4);
    dijkstra.addEdge(0, 2, 2);
    dijkstra.addEdge(1, 3, 5);
    dijkstra.addEdge(1, 4, 1);
    dijkstra.addEdge(2, 1, 1);
    dijkstra.addEdge(2, 3, 8);
    dijkstra.addEdge(2, 4, 10);
    dijkstra.addEdge(3, 4, 2);

    // 计算最短路径
    dijkstra.shortestPath(0);

    // 获取最短距离和路径
    cout << "Distance: " << dijkstra.getDistance(4) << endl;
    auto path = dijkstra.getPath(4);
    for (auto node : path) {
        cout << node << " ";
    }
    return 0;
}

输出结果为：

Distance: 5
0 2 1 4