dijkstra算法c++
时间: 2023-10-18 14:20:03 浏览: 34
以下是Dijkstra算法的C++代码实现,适用于有向图和无向图:
```c++
#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
// 定义边和权重的结构体
struct Edge {
int to; // 目标节点
int weight; // 权重
};
// 定义最短路径的结构体
struct ShortestPath {
vector<int> path; // 最短路径
int distance; // 距离
};
// Dijkstra算法实现函数
ShortestPath dijkstra(vector<vector<Edge>>& graph, int start, int end) {
int n = graph.size(); // 图的节点数
vector<int> dist(n, INT_MAX); // 存储起点到每个节点的距离
vector<int> prev(n, -1); // 存储最短路径上每个节点的前驱节点
vector<bool> visited(n, false); // 存储每个节点是否已经被访问
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; // 小根堆,存储距离和节点编号的pair
dist[start] = 0; // 起点到自身的距离为0
pq.push(make_pair(0, start)); // 把起点加入小根堆中
while (!pq.empty()) { // 小根堆不为空时循环
int u = pq.top().second; // 取出小根堆中距离最小的节点
pq.pop();
if (visited[u]) { // 如果该节点已经被访问,则跳过
continue;
}
visited[u] = true; // 标记该节点为已访问
for (const Edge& e : graph[u]) { // 遍历该节点的所有邻居节点
int v = e.to;
int w = e.weight;
if (dist[u] + w < dist[v]) { // 如果新路径的距离比原先记录的距离要小
dist[v] = dist[u] + w; // 更新最短距离
prev[v] = u; // 更新前驱节点
pq.push(make_pair(dist[v], v)); // 把该节点加入小根堆中
}
}
}
ShortestPath path;
path.distance = dist[end]; // 记录起点到终点的最短距离
int u = end;
while (u != -1) { // 从终点开始,沿着最短路径回溯到起点,记录路径上的节点
path.path.push_back(u);
u = prev[u];
}
reverse(path.path.begin(), path.path.end()); // 把路径翻转过来,变成起点到终点的顺序
return path;
}
int main() {
int n = 6; // 节点数
vector<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});
ShortestPath path = dijkstra(graph, 0, 4); // 求起点0到终点4的最短路径
// 输出最短路径和距离
cout << "Shortest Path: ";
for (int i : path.path) {
cout << i << " ";
}
cout << endl << "Shortest Distance: " << path.distance << endl;
return 0;
}
```
在上面的代码中,我们使用了邻接表表示法来存储有向图或无向图。函数`dijkstra`接受三个参数:邻接表表示的图、起点和终点。它返回一个`ShortestPath`类型的结构体,其中包含了最短路径和距离。我们使用小根堆来实现Dijkstra算法,每次取出距离最小的节点并更新它的邻居节点的最短距离和前驱节点。最后,我们从终点开始沿着最短路径回溯到起点,记录路径上的所有节点,并把它们翻转过来,就得到了起点到终点的最短路径。