根据以上代码请写出一个Dijkstra算法代码
时间: 2024-10-20 18:09:45 浏览: 18
Python实现Dijkstra算法
Dijkstra算法是一个用于查找有向图或无向图中最短路径的贪心算法。以下是根据给定代码片段整理出的一个简化版的Dijkstra算法实现,适用于单源最短路径问题:
```cpp
#include <iostream>
#include <vector>
#include <queue>
#include <limits.h>
// 使用优先队列存储待处理的顶点
using namespace std;
struct Node {
int vertex, distance;
bool operator<(const Node& other) const { return distance < other.distance; }
};
void dijkstra(int graph[][ma], int vertices, int src) {
vector<int> dist(vertices, INT_MAX); // 初始化距离数组,所有距离设为无穷大
dist[src] = 0; // 设置源节点的距离为0
priority_queue<Node, vector<Node>, less<Node>> pq; // 创建优先队列
pq.push({src, 0}); // 入队源节点
while (!pq.empty()) {
int u = pq.top().vertex;
pq.pop();
// 如果已经访问过该节点且当前距离更好,则无需更新
if (dist[u] < pq.top().distance)
continue;
// 遍历邻接节点并更新它们的距离
for (int v = 0; v < vertices; ++v) {
if (graph[u][v] != INT_MAX && dist[u] != INT_MAX &&
dist[u] + graph[u][v] < dist[v]) {
dist[v] = dist[u] + graph[u][v];
pq.push({v, dist[v]}); // 更新节点,并入队
}
}
}
// 打印结果
for (int i = 0; i < vertices; ++i) {
cout << "Vertex " << i << " is at a distance of " << dist[i] << " from the source.\n";
}
}
int main() {
int n, m;
cin >> n >> m;
int graph[n][ma];
// ... 这里需要根据实际输入读取图的权重矩阵 ...
dijkstra(graph, n, 0); // 从节点0开始运行Dijkstra算法
return 0;
}
```
这个版本的Dijkstra算法首先初始化距离数组和优先队列,然后不断取出距离当前已知最小的节点,更新其相邻节点的距离,并放入队列。直到队列为空,算法结束,此时得到的就是最短路径的长度及路径信息。注意,为了完整实现该算法,你需要提供一个具体的图结构(如邻接矩阵或邻接表)。
阅读全文