qt用优化队列实现dijkstra
时间: 2023-09-18 13:14:40 浏览: 33
以下是使用优先队列实现Dijkstra算法的C++代码:
```c++
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
const int INF = 0x3f3f3f3f;
struct Edge {
int to, w;
Edge(int to, int w) : to(to), w(w) {}
};
int n, m, s, t;
vector<Edge> g[MAXN];
int d[MAXN];
bool vis[MAXN];
void dijkstra() {
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
memset(d, INF, sizeof(d));
d[s] = 0;
q.push(make_pair(0, s));
while (!q.empty()) {
int u = q.top().second; q.pop();
if (vis[u]) continue;
vis[u] = true;
for (int i = 0; i < g[u].size(); i++) {
int v = g[u][i].to, w = g[u][i].w;
if (d[v] > d[u] + w) {
d[v] = d[u] + w;
q.push(make_pair(d[v], v));
}
}
}
}
int main() {
cin >> n >> m >> s >> t;
for (int i = 1; i <= m; i++) {
int u, v, w;
cin >> u >> v >> w;
g[u].push_back(Edge(v, w));
g[v].push_back(Edge(u, w));
}
dijkstra();
cout << d[t] << endl;
return 0;
}
```
其中,使用了STL中的优先队列(priority_queue)来实现优化。每次从队列中取出距离起点最近的顶点,更新与之相邻的顶点的距离,并将其加入队列中。算法的时间复杂度为O(mlogn),其中m是边数,n是顶点数。
相关推荐
![py](https://img-home.csdnimg.cn/images/20210720083646.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_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_ask_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)
![](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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)