qt用dijkstra邻接链表算最短路径
时间: 2023-09-15 09:22:59 浏览: 45
以下是一个使用Dijkstra算法和邻接链表来计算最短路径的示例代码:
```
#include <iostream>
#include <vector>
#include <queue>
#include <limits>
using namespace std;
const int INF = numeric_limits<int>::max();
struct Edge {
int to;
int weight;
Edge(int t, int w) : to(t), weight(w) {}
};
typedef vector<vector<Edge>> Graph;
vector<int> dijkstra(const Graph& graph, int start) {
int n = graph.size();
vector<int> dist(n, INF);
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 u = pq.top().second;
pq.pop();
for (const auto& e : graph[u]) {
int v = e.to;
int w = e.weight;
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
pq.push(make_pair(dist[v], v));
}
}
}
return dist;
}
int main() {
int n, m, s, t;
cin >> n >> m >> s >> t;
Graph graph(n);
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
graph[u].push_back(Edge(v, w));
graph[v].push_back(Edge(u, w));
}
vector<int> dist = dijkstra(graph, s);
cout << dist[t] << endl;
return 0;
}
```
在这个示例代码中,我们首先通过输入读取图的节点数和边数,起点和终点。然后,我们创建了一个邻接链表形式的图,并通过输入读取每个边的起点、终点和权重。接下来,我们调用dijkstra函数来计算起点到所有其他节点的最短路径,并将结果存储在dist向量中。最后,我们输出终点的最短路径长度。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_lunwen.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)