dijkstra算法c++
时间: 2023-08-03 16:15:11 浏览: 37
Dijkstra算法是一种用于计算加权图中最短路径的贪心算法。以下是Dijkstra算法的C++实现:
```c++
#include<bits/stdc++.h>
using namespace std;
const int INF=1e9+7;
const int MAXN=1e5+5;
vector<pair<int,int>>vec[MAXN];
int n,m,s;
int dis[MAXN],vis[MAXN];
void dijkstra(int s){
memset(dis,0x3f,sizeof(dis));
dis[s]=0;
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>q;
q.push({0,s});
while(!q.empty()){
int u=q.top().second;q.pop();
if(vis[u]) continue;
vis[u]=1;
for(auto p:vec[u]){
int v=p.first,w=p.second;
if(dis[v]>dis[u]+w){
dis[v]=dis[u]+w;
q.push({dis[v],v});
}
}
}
}
int main(){
scanf("%d%d%d",&n,&m,&s);
for(int i=1;i<=m;i++){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
vec[u].push_back({v,w});
}
dijkstra(s);
for(int i=1;i<=n;i++){
if(dis[i]==INF) printf("INF ");
else printf("%d ",dis[i]);
}
return 0;
}
```
该实现使用了一个优先队列来维护未访问节点的最小距离。由于Dijkstra算法使用了贪心策略,每次选择距离起点最近的未访问节点,因此可以保证最短路径的正确性。