迪特斯特拉算法c++打印
时间: 2023-07-26 08:06:29 浏览: 41
以下是使用 C++ 实现的 Dijkstra 算法,并输出最短路径的代码示例:
```c++
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define INF 0x3f3f3f3f
typedef pair<int, int> iPair;
class Graph {
int V;
vector<pair<int, int>>* adj;
public:
Graph(int V) {
this->V = V;
adj = new vector<iPair>[V];
}
void addEdge(int u, int v, int w) {
adj[u].push_back(make_pair(v, w));
adj[v].push_back(make_pair(u, w));
}
void dijkstra(int src) {
priority_queue<iPair, vector<iPair>, greater<iPair>> pq;
vector<int> dist(V, INF);
pq.push(make_pair(0, src));
dist[src] = 0;
while (!pq.empty()) {
int u = pq.top().second;
pq.pop();
for (auto i = adj[u].begin(); i != adj[u].end(); ++i) {
int v = i->first;
int weight = i->second;
if (dist[v] > dist[u] + weight) {
dist[v] = dist[u] + weight;
pq.push(make_pair(dist[v], v));
}
}
}
cout << "Vertex\tDistance from source" << endl;
for (int i = 0; i < V; ++i)
cout << i << "\t" << dist[i] << endl;
}
};
int main() {
Graph g(6);
g.addEdge(0, 1, 5);
g.addEdge(0, 2, 1);
g.addEdge(1, 2, 2);
g.addEdge(1, 3, 3);
g.addEdge(2, 3, 4);
g.addEdge(3, 4, 6);
g.addEdge(2, 4, 7);
g.dijkstra(0);
return 0;
}
```
该代码使用了 STL 中的 vector 和 priority_queue,其中 vector 存储每个节点到其它节点的边及其权重,priority_queue 存储每个节点到源节点的距离及其节点编号,以便按照距离从小到大依次访问。在 dijkstra 函数中,首先将源节点加入 priority_queue 中,并将其距离设为 0。接着,依次访问 priority_queue 中的每个节点,并遍历它的邻居节点,更新它们到源节点的距离。最后,输出每个节点到源节点的最短距离。