使用C++语言写一段实现dijkstra算法的代码,要用到vector
时间: 2024-02-26 20:57:35 浏览: 60
dijkstra 算法的c++实现
以下是使用 C++ 实现 Dijkstra 算法的示例代码,其中使用了 vector 作为容器:
```c++
#include<bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
// 定义节点类
class node {
public:
int to, weight;
node(int _to, int _weight) : to(_to), weight(_weight) {}
};
// 定义图类
class Graph {
private:
int n;
vector<vector<node>> adjList;
public:
Graph(int _n) : n(_n) {
adjList.resize(n);
}
void addEdge(int from, int to, int weight) {
adjList[from].push_back(node(to, weight));
}
void dijkstra(int start) {
vector<int> dist(n, INF);
dist[start] = 0;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
pq.push({ 0, start });
while (!pq.empty()) {
int u = pq.top().second;
pq.pop();
for (auto& v : adjList[u]) {
if (dist[v.to] > dist[u] + v.weight) {
dist[v.to] = dist[u] + v.weight;
pq.push({ dist[v.to], v.to });
}
}
}
// 输出每个节点到起点的最短距离
for (int i = 0; i < n; ++i) {
cout << "Node " << i << " distance from start: " << dist[i] << endl;
}
}
};
int main() {
// 创建图
Graph g(6);
g.addEdge(0, 1, 4);
g.addEdge(0, 2, 2);
g.addEdge(1, 2, 1);
g.addEdge(1, 3, 5);
g.addEdge(2, 3, 8);
g.addEdge(2, 4, 10);
g.addEdge(3, 4, 2);
g.addEdge(3, 5, 6);
g.addEdge(4, 5, 1);
// 运行 Dijkstra 算法
g.dijkstra(0);
return 0;
}
```
以上代码创建了一个 `Graph` 类来表示图,其中使用 `adjList` 作为邻接表存储图中的边。`dijkstra` 方法使用了优先队列来实现 Dijkstra 算法,计算起点到图中各个节点的最短距离,并输出结果。
阅读全文