最短路——dijkstra（学习笔记）
XichenOC
·
·
算法·理论
dijkstra
例题 P4779 【模板】单源最短路径（标准版）
作用：
dijkstra是一种用来处理非负边权的单源最短路，在特定情况下，他比其他常用算法都较快。在做图论时有较大用处。
算法原理：
1.先定义两个集合$A$和$B$，$A$集合里的元素是还未算出最短路的点;$B$集合里的就是已经求出最短路的点。
2.而我们要做的就是从起点开始遍历每一个点。每次都找到最短的那个边，再将它加入$A$（即有一个点$q$到另一个点$p$有多条边，$q \rightarrow p$的最短路就是最短的那条，依次类推）。若用暴力搜索最短的边，那整体的时间复杂度为 $n^2$,因为每次只需要最短的一条边，因此可以用小根堆维护，复杂度为$nlogn$。
# 完整代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=100010;
struct edge{
int v,w;
};
struct node{
int dis,u;
bool operator>(const node& a)const{return dis>a.dis;}
};
int dis[N],vis[N];
vector<edge>e[N];
priority_queue<node,vector<node>,greater<node>>q;
void dijkstra(int s){
memset(dis,0x3f,sizeof(dis));
dis[s]=0;
q.push({0,s});
while(!q.empty()){
int u=q.top().u;
q.pop();
if(vis[u])continue;
vis[u]=1;
for(auto ed:e[u]){
int w=ed.w,v=ed.v;
if(dis[v]>dis[u]+w){
dis[v]=dis[u]+w;
q.push({dis[v],v});
}
}
}
}
int main(){
int n,m,s;
cin>>n>>m>>s;
for(int i=1;i<=m;i++){
int u,v,w;
cin>>u>>v>>w;
e[u].push_back({v,w});
}
dijkstra(s);
for(int i=1;i<=n;i++)cout<<dis[i]<<" ";
}
```
# 注意：
一般来说，最短路的题，都是难于建图，要找到题目的要求。再使用模板
# 普通 $dijkstra$:
这里也放上普通版 $dijkstra$ 的代码，要根据题目的 点数 $n$ 和边数 $m$ 来合理选择使用，若 $m$ 较大，而 $n$ 较少，则用普通版可能更优。
```cpp
void dijkstra(){
memset(dis,0x3f,sizeof(dis));
memset(vis,0,sizeof(vis));
dis[1]=0;
for(int i=1;i<=n;i++){
int u=0,mi=0x3f3f3f3f;
for(int j=1;j<=n;j++){
if(dis[j]<mi && !vis[j]){
mi=dis[j];
u=j;
}
}
vis[u]=1;
for(auto ed:e[u]){
int v=ed.v,w=ed.w;
if(dis[v]>dis[u]+w){
dis[v]=dis[u]+w;
}
}
}
}
```
# 练习：
[$1.$P2984 [USACO10FEB] Chocolate Giving S](https://www.luogu.com.cn/problem/P2984) [**题解**](https://www.luogu.com.cn/article/8lxrltad)
[$2.$P1396 营救](https://www.luogu.com.cn/problem/P1396) [**题解**](https://www.luogu.com.cn/article/31edfr49)
[$3.Cheap Robot$](https://www.luogu.com.cn/problem/CF1253F) [**题解**](https://www.luogu.com.cn/article/3aql7yl6)
[$4.$P2176 [USACO11DEC] RoadBlock S / [USACO14FEB]Roadblock G/S](https://www.luogu.com.cn/problem/P2176) [**题解**](https://www.luogu.com.cn/article/bpqi58wv)
[$5.$P1186 玛丽卡](https://www.luogu.com.cn/problem/P1186) [**题解**](https://www.cnblogs.com/XichenOC/p/18686700)