dijstra 算法c++
时间: 2023-07-26 11:13:08 浏览: 45
以下是一个简单的C++实现Dijkstra算法的示例代码:
```c++
#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
// 定义边结构体
struct Edge {
int to; // 边的终点
int weight; // 边的权重
Edge(int to, int weight) : to(to), weight(weight) {}
};
// Dijkstra算法
vector<int> dijkstra(vector<vector<Edge>> &graph, int start) {
int n = graph.size();
vector<int> dist(n, INT_MAX);
vector<bool> visited(n, false);
dist[start] = 0;
// 定义优先队列,用于存储待扩展的节点
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
q.push({0, start});
// Dijkstra算法的主循环
while (!q.empty()) {
auto curr = q.top();
q.pop();
int u = curr.second;
if (visited[u]) continue;
visited[u] = true;
for (auto e : graph[u]) {
int v = e.to, w = e.weight;
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
q.push({dist[v], v});
}
}
}
return dist;
}
// 测试
int main() {
vector<vector<Edge>> graph = {
{Edge(1, 4), Edge(2, 1)},
{Edge(2, 2), Edge(3, 5)},
{Edge(3, 1)},
{Edge(0, 6)}
};
vector<int> dist = dijkstra(graph, 0);
for (int d : dist) {
cout << d << " ";
}
cout << endl;
return 0;
}
```
这里使用了一个Edge结构体来表示每条边的信息,使用了一个距离数组来记录起点到每个节点的最短距离,使用了一个visited数组来记录每个节点是否已经被访问过,使用了一个优先队列来存储待扩展的节点。在Dijkstra算法的主循环中,每次从优先队列中取出距离起点最短的节点进行扩展,如果找到了终点,则直接返回距离数组。