dijkstra算法c++类模板实现
时间: 2023-08-02 17:06:22 浏览: 37
好的,下面是Dijkstra算法的C++类模板实现:
```c++
#include <vector>
#include <queue>
#include <limits>
using namespace std;
template<typename T>
class Dijkstra{
private:
// 定义INF为T类型的最大值
const T INF = numeric_limits<T>::max();
// 存储图的邻接表
vector<vector<pair<int, T>>> adj;
public:
// 构造函数
Dijkstra(int n){
adj.resize(n);
}
// 添加一条有向边
void addEdge(int u, int v, T w){
adj[u].emplace_back(v, w);
}
// 计算从源点s到各个点的最短距离
vector<T> shortestPath(int s){
// 存储最短距离
vector<T> dist(adj.size(), INF);
// 定义优先队列,pair第一个元素为距离,第二个元素为顶点编号
priority_queue<pair<T, int>, vector<pair<T, int>>, greater<pair<T, int>>> pq;
// 将源点加入优先队列
pq.emplace(0, s);
dist[s] = 0;
while(!pq.empty()){
auto cur = pq.top();
pq.pop();
// 如果当前距离大于最短距离,说明已经处理过该点,跳过
if(cur.first > dist[cur.second]){
continue;
}
// 遍历当前点的邻接点
for(auto next : adj[cur.second]){
// 计算从源点到next的距离
T d = cur.first + next.second;
// 如果距离小于当前最短距离,更新最短距离
if(d < dist[next.first]){
dist[next.first] = d;
pq.emplace(d, next.first);
}
}
}
return dist;
}
};
```
使用示例:
```c++
int main(){
int n = 5;
Dijkstra<int> dijkstra(n);
dijkstra.addEdge(0, 1, 2);
dijkstra.addEdge(1, 2, 3);
dijkstra.addEdge(2, 4, 1);
dijkstra.addEdge(0, 3, 5);
dijkstra.addEdge(3, 4, 4);
vector<int> dist = dijkstra.shortestPath(0);
// 输出从源点0到各个点的最短距离
for(int i = 0; i < n; i++){
cout << "dist[" << i << "] = " << dist[i] << endl;
}
return 0;
}
```