浅谈Dijkstra

一.前言

有一说一,今天心情极度不佳,于是找来了一直似懂非懂的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--------------------------------------------------------------------

上一篇:双向Dijkstra算法、Dijkstra算法对比


下一篇:【算法】Dijkstra算法求最短路径