一.前言
有一说一,今天心情极度不佳,于是找来了一直似懂非懂的Dijkstra来做......
Dijkstra是一种求最短路径的算法,学名叫单源最短路,这里的源指的是起点,即dijkstra仅能计算唯一起点对应多个终点的问题,和BFS十分相似。
和其他的算法类似,dijkstra有很多种变形,本文主要讲解堆优化版的,其他例如小根堆、线段树实现什么的请大家自行探索其实我不会。
二.存图
众所周知,dijkstra是依赖于图的,所以抛开图讲dijkstra无异于耍流氓。对于刚接触的OIer来说,学习新的(指模拟链表而非邻接矩阵)存图方式是很有必要的。
前面提到,dijkstra和BFS是很像的,简单来说,它的中心思想是通过查看每条边的权值来决定是否松弛,就像做事情总得有一个顺序,我们需要在存图时记录这个路径。
void add(int x, int y, int z){
e[++cnt].st = x, e[cnt].to = y, e[cnt].w = z;
e[cnt].next = head[x], head[x] = cnt;
}
值得注意的,这里的st参数并无卵用,但为了方便大家理解(即start),st指起点,to指终点,w是花费,next指上一条共起点的边的终点,head[x]则指上一条边加入的边号。
三.重载运算符及优先队列
堆优化的dijkstra为什么优?就是因为有了重载运算符和优先队列。
重载运算符和优先队列可以保证新加入的边一定按照自己w的值插入合适的位置(升序排列)。
重载运算符可以写在结构体里,也可以单独拎出来写,我个人习惯后一个。
struct po{ //po数组
int a, b;//a用来记录当前点,b记录起点到a的距离
};
bool operator < (po x, po y){
return x.b > y.b;
}
优先队列是STL库里的函数,直接使用就行。
priority_queue <po> q;
四.dijkstra主函数
当做好前面的准备工作后,就可以写dijkstra了。
void dijkstra(){
for(int i = 1; i <= n; i++) lc[i] = 0x3f3f3f3f;
lc[s] = 0;
priority_queue <po> q;
memset(vis,0,sizeof(vis));
po st; st.a = s, st.b = 0;
q.push(st);
while(!q.empty()){
po now = q.top(); q.pop();
if(vis[now.a]) continue; vis[now.a] = 1;
for(int i = head[now.a]; i; i = e[i].next){
lc[e[i].to] = min(lc[e[i].to], lc[now.a] + e[i].w);
po jia; jia.a = e[i].to; jia.b = lc[e[i].to];
q.push(jia);
}
}
}
十分通俗易懂,lc[x]代表指x到s的距离,s是起点。至于后面的循环,学过搜索的都懂,没学过搜索的学完搜索也会懂。
最后放上完整版代码:
#include<bits/stdc++.h>
using namespace std;
struct edge{
int st, to, next, w;
}e[500005];
int n, m, s, u, v, w, cnt, lc[200005], head[200005], vis[200005];
void add(int x, int y, int z){
e[++cnt].to = y, e[cnt].st = x, e[cnt].w = z;
e[cnt].next = head[x], head[x] = cnt;
}
struct po{
int a, b;
};
bool operator < (po x, po y){
return x.b > y.b;
}
void dijkstra(){
for(int i = 1; i <= n; i++) lc[i] = 0x3f3f3f3f;
lc[s] = 0;
priority_queue <po> q;
po st; st.a = s, st.b = 0;
q.push(st);
while(!q.empty()){
po now = q.top(); q.pop();
if(vis[now.a]) continue; vis[now.a] = 1;
for(int i = head[now.a]; i; i = e[i].next){
if(lc[e[i].to] > lc[now.a] + e[i].w){
lc[e[i].to] = lc[now.a] + e[i].w;
po jia; jia.a = e[i].to, jia.b = lc[e[i].to];
q.push(jia);
}
}
}
}
int main(){
scanf("%d%d%d", &n, &m, &s);
for(int i = 1; i <= m; i++){
scanf("%d%d%d", &u, &v, &w);
add(u, v, w);
}
dijkstra();
for(int i = 1; i <= n; i++){
printf("%d ", lc[i]);
}
return 0;
}
以上代码可以 AC luogu 的dijkstra模板题,建议大家自己打打试试,有点想法之后便可以做几道题巩固一下。本文也只是对自己知识的总结,如有纰漏还请各位大佬指出(虽然我知道根本没人看我博客)~~
五.后记
其实dijkstra很早之前就有在学了,只是我菜学不懂,就先学了并查集。感觉并查集简单的,可能是我对BFS有点抵触心理的缘故,时至今日才完全搞懂dijkstra,去做了道题却只有30pts,决定去颓炉石,话说有小伙伴一起下棋吗?
-------------------------------------------------------------End--------------------------------------------------------------------