C++实现dijkstra
时间: 2023-09-03 13:13:53 浏览: 45
当然可以!下面是一个简单的C++实现Dijkstra算法的示例代码:
```cpp
#include <iostream>
#include <vector>
#include <queue>
#include <limits>
using namespace std;
const int INF = numeric_limits<int>::max();
// 边的结构体
struct Edge {
int to;
int weight;
};
// 图的结构体
struct Graph {
int vertexCount;
vector<vector<Edge>> adjList;
};
// Dijkstra算法
vector<int> dijkstra(const Graph& graph, int source) {
vector<int> distances(graph.vertexCount, INF); // 初始化距离为无穷大
distances[source] = 0; // 起点到自身的距离为0
// 优先队列用于选择最短距离的顶点
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
pq.push({0, source});
while (!pq.empty()) {
int u = pq.top().second; // 当前最短距离的顶点
pq.pop();
// 遍历与u相邻的顶点
for (const Edge& edge : graph.adjList[u]) {
int v = edge.to;
int weight = edge.weight;
// 如果经过u到达v的距离更短,则更新距离并加入优先队列
if (distances[u] + weight < distances[v]) {
distances[v] = distances[u] + weight;
pq.push({distances[v], v});
}
}
}
return distances;
}
int main() {
Graph graph;
graph.vertexCount = 6; // 图中顶点的数量
// 构建图的邻接表表示
graph.adjList.resize(graph.vertexCount);
graph.adjList[0].push_back({1, 2}); // 添加边
graph.adjList[0].push_back({2, 5});
graph.adjList[1].push_back({2, 2});
graph.adjList[1].push_back({3, 1});
graph.adjList[2].push_back({1, 3});
graph.adjList[2].push_back({3, 4});
graph.adjList[2].push_back({4, 2});
graph.adjList[3].push_back({4, 3});
graph.adjList[3].push_back({5, 4});
graph.adjList[4].push_back({5, 1});
int source = 0; // 起点
vector<int> distances = dijkstra(graph, source);
// 输出最短距离
for (int i = 0; i < graph.vertexCount; i++) {
cout << "Distance from " << source << " to " << i << " is " << distances[i] << endl;
}
return 0;
}
```
这段代码实现了Dijkstra算法,使用了图的邻接表来表示图的结构。你可以根据自己的需求修改顶点数量和边的连接关系。希望对你有帮助!