qt用dijkstra邻接链表算最短路径
时间: 2024-03-13 15:37:40 浏览: 22
以下是使用Dijkstra算法和邻接链表实现最短路径的示例代码:
```cpp
#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
const int MAXN = 10005;
struct Edge {
int to;
int weight;
Edge(int t, int w) : to(t), weight(w) {}
};
vector<Edge> graph[MAXN]; // 邻接链表存储图
int dist[MAXN]; // 存储起点到各个顶点的距离
bool visited[MAXN]; // 标记该点是否已经被访问过
void dijkstra(int start) {
// 初始化
fill(dist, dist + MAXN, INT_MAX);
fill(visited, visited + MAXN, false);
dist[start] = 0;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
pq.push(make_pair(0, start));
while (!pq.empty()) {
int curr = pq.top().second;
pq.pop();
if (visited[curr]) {
continue;
}
visited[curr] = true;
for (Edge& e : graph[curr]) {
int next = e.to;
int weight = e.weight;
if (dist[curr] + weight < dist[next]) {
dist[next] = dist[curr] + weight;
pq.push(make_pair(dist[next], next));
}
}
}
}
int main() {
// 添加图的边
graph[1].push_back(Edge(2, 2));
graph[1].push_back(Edge(3, 3));
graph[2].push_back(Edge(3, 1));
graph[2].push_back(Edge(4, 2));
graph[2].push_back(Edge(5, 1));
graph[3].push_back(Edge(4, 2));
graph[4].push_back(Edge(5, 4));
dijkstra(1);
// 输出起点到各个顶点的最短距离
for (int i = 1; i <= 5; i++) {
cout << "Distance from 1 to " << i << " is " << dist[i] << endl;
}
return 0;
}
```
在上面的代码中,我们首先定义了一个结构体`Edge`来表示一条边,其中包含了边的终点和权重。然后定义了一个邻接链表来存储图的信息,每个节点记录了所有出边的信息。在`dijkstra`函数中,我们使用了一个最小堆来维护当前未访问的顶点中距离起点最近的顶点。在每次从堆中取出一个顶点后,我们遍历该顶点的所有出边,更新到达每个出边终点的最短距离,并将其加入堆中。最后,我们输出起点到各个顶点的最短距离。
需要注意的是,在本示例代码中,我们使用了`INT_MAX`来表示距离的初始值,这是一个较大的数值,相当于无穷大。在实际应用中,我们可能需要根据具体情况选择不同的初始值。此外,我们还需要注意遍历每个顶点的所有出边时,需要使用引用`&`来避免拷贝。