dijkstra算法c++类模板实现
时间: 2023-08-02 12:05:44 浏览: 42
以下是Dijkstra算法的C++类模板实现:
```c++
#include <iostream>
#include <vector>
#include <queue>
#include <limits.h>
using namespace std;
template<typename T>
class Dijkstra
{
public:
Dijkstra(int n) : adj(n), dist(n, numeric_limits<T>::max()), visited(n, false) {}
void addEdge(int u, int v, T w)
{
adj[u].push_back(make_pair(v, w));
adj[v].push_back(make_pair(u, w));
}
void shortestPath(int start)
{
priority_queue<pair<int, T>, vector<pair<int, T>>, greater<pair<int, T>>> pq;
pq.push(make_pair(start, 0));
dist[start] = 0;
while (!pq.empty())
{
int u = pq.top().first;
pq.pop();
if (visited[u])
continue;
visited[u] = true;
for (auto& p : adj[u])
{
int v = p.first;
T w = p.second;
if (dist[v] > dist[u] + w)
{
dist[v] = dist[u] + w;
pq.push(make_pair(v, dist[v]));
}
}
}
}
T getDistance(int u)
{
return dist[u];
}
private:
vector<vector<pair<int, T>>> adj;
vector<T> dist;
vector<bool> visited;
};
int main()
{
int n = 5;
Dijkstra<int> dijkstra(n);
dijkstra.addEdge(0, 1, 2);
dijkstra.addEdge(0, 3, 1);
dijkstra.addEdge(1, 2, 3);
dijkstra.addEdge(1, 3, 2);
dijkstra.addEdge(2, 4, 1);
dijkstra.addEdge(3, 4, 4);
dijkstra.shortestPath(0);
for (int i = 0; i < n; i++)
cout << "Distance from 0 to " << i << ": " << dijkstra.getDistance(i) << endl;
return 0;
}
```
该类模板实现了Dijkstra算法,使用了邻接表来表示图,`addEdge`函数用于添加边,`shortestPath`函数用于计算从起点到其他点的最短距离,`getDistance`函数用于获取某个点到起点的最短距离。在main函数中,我们通过创建一个Dijkstra对象,添加边并调用`shortestPath`函数来计算最短路径。