dijkstra算法c++类模板实现

以下是Dijkstra算法的C++类模板实现示例：

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

template <typename T>
class Dijkstra {
public:
    Dijkstra(const std::vector<std::vector<std::pair<int, T>>>& graph, int source) : 
        graph_(graph), dist_(graph.size(), std::numeric_limits<T>::max()), 
        visited_(graph.size(), false), source_(source) {}

    void run() {
        dist_[source_] = 0;
        std::priority_queue<std::pair<T, int>, std::vector<std::pair<T, int>>, std::greater<>> pq;
        pq.emplace(0, source_);

        while (!pq.empty()) {
            int u = pq.top().second;
            pq.pop();

            if (visited_[u]) continue;
            visited_[u] = true;

            for (const auto& [v, weight] : graph_[u]) {
                if (dist_[u] + weight < dist_[v]) {
                    dist_[v] = dist_[u] + weight;
                    pq.emplace(dist_[v], v);
                }
            }
        }
    }

    T get_distance(int target) const {
        return dist_[target];
    }

private:
    const std::vector<std::vector<std::pair<int, T>>>& graph_;
    std::vector<T> dist_;
    std::vector<bool> visited_;
    const int source_;
};

int main() {
    std::vector<std::vector<std::pair<int, int>>> graph = {
        {{1, 4}, {2, 1}},
        {{3, 1}},
        {{1, 2}, {3, 5}},
        {{4, 3}},
        {{0, 1}}
    };

    Dijkstra<int> dijkstra(graph, 0);
    dijkstra.run();

    std::cout << dijkstra.get_distance(4) << '\n'; // output: 2
}

在上面的代码中，我们使用了一个类模板 `Dijkstra` 来实现Dijkstra算法。我们的 `Dijkstra` 类接受一个加权图 `graph` 和一个起点 `source` 作为输入，并计算出起点到其他所有顶点的最短路径。

`Dijkstra` 类中的 `run()` 函数是算法的主体，它遍历所有顶点，并使用一个优先队列来选择下一个要访问的顶点。我们使用 `dist_` 向量来存储从起点到每个顶点的最短距离，并使用 `visited_` 向量来标记已经访问过的顶点。

在 `get_distance()` 函数中，我们可以查询从起点到目标顶点的最短距离。

在主函数中，我们使用一个示例图来测试 `Dijkstra` 类。我们首先创建一个 `graph`，然后创建一个 `Dijkstra` 对象并运行它。最后，我们输出从起点到目标顶点的最短距离。