Dijkstra c++14 朴素模板

Dijkstra算法是一种用于寻找图中两点之间最短路径的经典算法。在C++14中，你可以使用模板来编写一个通用的Dijkstra实现，适用于不同类型的数据结构（如邻接矩阵或邻接表）。下面是一个简化的模板版本，假设我们使用`std::pair<int, int>`来表示节点之间的权重和距离：

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

template <typename T, typename Weight = std::pair<int, int>>
struct Graph {
    // ...定义节点和边的结构...
};

template <typename Graph, typename Distance = typename Graph::Weight>
class Dijkstra {
public:
    void dijkstra(const Node& start) {
        priority_queue<std::pair<Distance, Node>, std::vector<std::pair<Distance, Node>>, std::greater<Distance>> pq;
        visited[start.index] = true;
        pq.push(std::make_pair(start.distance, start));

        while (!pq.empty()) {
            auto current = pq.top(); pq.pop();
            if (visited[current.second.index]) continue;

            // 更新邻居的最短距离
            for (const auto& neighbor : current.second.neighbors) {
                const Distance new_distance = current.first + neighbor.weight;
                if (!visited[neighbor.index] || new_distance < distances[neighbor.index]) {
                    distances[neighbor.index] = new_distance;
                    pq.push(std::make_pair(new_distance, neighbor));
                }
            }
        }
    }

private:
    std::vector<bool> visited;
    std::vector<Distance> distances; // 存储每个节点的已知最短距离
};

// 使用示例：
int main() {
    Graph<int> graph; // 假设这是你的图实例
    Dijkstra(Graph<int>, std::make_pair<int, int>> dijkstra(graph);
    dijkstra.dijkstra(graph.get_start_node());
    return 0;
}

在这个例子中，`T`代表图中的节点类型，而`Weight`则是节点之间的权重类型。注意，这只是一个基础模板，并未包含所有细节，如处理无权图或负权重的情况。