Dijkstra算法C++
时间: 2023-09-24 11:12:23 浏览: 64
Dijkstra算法是一种用于图中寻找最短路径的算法。下面是一个用C++实现Dijkstra算法的示例代码:
```cpp
#include <iostream>
#include <vector>
#include <queue>
#include <limits>
#define INF std::numeric_limits<int>::max()
struct Edge {
int to;
int weight;
};
void dijkstra(std::vector<std::vector<Edge>>& graph, int start, std::vector<int>& dist) {
int n = graph.size();
dist.resize(n, INF);
dist[start] = 0;
std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<std::pair<int, int>>> pq;
pq.push(std::make_pair(0, start));
while (!pq.empty()) {
int u = pq.top().second;
pq.pop();
for (const auto& edge : graph[u]) {
int v = edge.to;
int weight = edge.weight;
if (dist[u] != INF && dist[u] + weight < dist[v]) {
dist[v] = dist[u] + weight;
pq.push(std::make_pair(dist[v], v));
}
}
}
}
int main() {
int n = 6; // 图中节点的数量
std::vector<std::vector<Edge>> graph(n);
// 添加图的边
graph[0].push_back({1, 7});
graph[0].push_back({2, 9});
graph[0].push_back({5, 14});
graph[1].push_back({2, 10});
graph[1].push_back({3, 15});
graph[2].push_back({3, 11});
graph[2].push_back({5, 2});
graph[3].push_back({4, 6});
graph[4].push_back({5, 9});
int start = 0; // 起始节点
std::vector<int> dist;
dijkstra(graph, start, dist);
// 输出最短路径
for (int i = 0; i < n; ++i) {
std::cout << "从节点" << start << "到节点" << i << "的最短距离为:" << dist[i] << std::endl;
}
return 0;
}
```
这段代码实现了Dijkstra算法,并输出了从指定起始节点到每个节点的最短距离。你可以根据自己的需求修改图的边和起始节点来运行并验证算法的正确性。