算法之Dijkstra及其堆优化和SPFA：图上单源最短路径神器

签到题……

SPFA算法

本人曾经写过一篇有关Bellman-ford的博，但就算是挂了优化的ford也只能过这道题的弱化版。

今天就先填个坑，先讲SPFA。

在这里我直接认为你们已经有一定图论基础，至少知道啥是松弛之类的……

什么？你不知道？请移步百度……

spfa算法的一般时间复杂度：\(O(KM)\)，M为边数，K为每个节点平均进队次数，经测试接近4，所以spfa一般情况下是很高效的。

spfa算法的最坏时间复杂度：\(O(NM)\)，spfa算法可以被恶意卡到与bellman-ford一样的效率。

spfa被认为在随机的稀疏图中表现出色。

SPFA伪代码：

queue<int>q;//这个队列可是spfa的重点所在！

int n,m,s;//n是点数，m是边数，s是源点

struct node{

	int to,val;//用来邻接表存图的结构体，to是目标点，val是边权值

};

int dis[10001];//distance数组不用说

bool vis[10001];//vis数组的作用是标记是否在队列中

vector<node>gragh[10001];//邻接表存图

inline void spfa(){

	for(int i=1;i<=n;i++){

		if(i==s)continue;

		dis[i]=0x3f3f3f3f;

	}

        //这个初始化，不用说。

	int t;//t是当前到哪个点了

	q.push(s);//q队列最开始push进s去

	vis[s]=1;//给s点一个标记

	while(!q.empty()){//spfa终止的标志是队列为空

		t=q.front();q.pop();//我们取出队头的这个元素，赋给t

		for(int i=0;i<gragh[t].size();i++){//遍历所有与t相连的点

			if(dis[t]+gragh[t][i].val<dis[gragh[t][i].to]){//如果满足松弛条件

                                                                       //注意这里，我们是满足松弛条件才进行松弛，而不是直接一个min解决，这是因为松弛后紧跟的是入队操作，也是spfa进行常数优化的重点

				dis[gragh[t][i].to]=dis[t]+gragh[t][i].val;//松弛操作

				if(!vis[gragh[t][i].to]){//判断，若被松弛的点没入队

					q.push(gragh[t][i].to);//直接入队

					vis[gragh[t][i].to]=1;//打上标记

				}

			}

		}

		vis[t]=0;//别忘了我们在开头把t点pop出来了，要把标记消掉。

	}

}

本人的马蜂清奇，可能有人看不懂这个邻接表啥意思，实际很简单啊，我来贴一下输入代码就明白了

for(int i=1;i<=m;i++){

	scanf("%d %d %d",&u,&v,&w);//依次输入入点，出点，边权值

	gragh[u].push_back({v,w});//在入点那个vector里push一下destination和value。

}

我们来讲一下spfa是怎么对bellman-ford优化的：

首先，明确一点，一个点什么时候必须需要松弛操作？当且仅当与它相连的点发生了松弛时！

q队列中存放的时是进行了松弛后所影响到的有待松弛的点。

vis数组是给正在队列中的元素打标记的，防止元素重复进入队列。

这几句明白了，spfa基本就明白了。

spfa的基本思路：

初始化，将起点扔进队列，打上标记
把队头元素取出，并遍历与之相连的节点，如果能进行松弛则前往步骤3，不能跳过
对该节点进行松弛，如果该节点在队列中，跳过，不在队列中进行步骤4
将该节点扔进队列。
遍历结束后，消除原队头元素的标记（就是我们在步骤2中拿出来的那个），然后重复步骤2直到队列为空。

到这里，spfa就讲完了，蒟蒻自认为讲的很清楚……

dijkstra算法

原始算法

dijkstra算法是巧妙运用贪心求图上单源最短路径的算法，时间复杂度为\(O(n^2)\)

dijkstra只适用于边权为正的图，如果为负，则贪心性质遭到破坏。

伪代码：

int n,m,s;

bool vis[maxn];

int dis[amxn];

int now=s;

memset(dis,0x3f,sizeof(dis));

dis[sourse]=0;

struct node{

    int to,val;

}

vector<node>gragh[maxn];

//算法主体开始

while(!vis[now]){

    for(int i=0;i<gragh[now].size();i++){

    	dis[gragh[now][i].to]=min(dis[gragh[now][i].to],dis[now]+gragh[now][i].val);

    }//对当前节点进行松弛操作

    vis[now]=1;//给当前节点打标记

    int minn=0x3f3f3f3f;

    for(int i=1;i<=n;i++){//遍历所有点，在没有被打标记的点中找到dis最小的点，更新为now

    	if(vis[i]==0&&ans[i]<minn){

            minn=ans[i];

            now=i;

        }

    }

}

算法基本思路：

初始化，同其他算法基本一致
对当前点进行松弛，标记。
在没有被打标记的点中找到dis最小的点，更新当前点
重复2，直到所有点都被标记

思路大致就是这么个思路，但是，裸的dijkstra还是不行，我们为了追求更快的速度，看到了这里：

for(int i=1;i<=n;i++){//遍历所有点，在没有被打标记的点中找到dis最小的点，更新为now

    if(vis[i]==0&&ans[i]<minn){

        minn=ans[i];

        now=i;

    }

}

既然是动态维护序列最小值，我们想到了优先队列

堆优化

伪代码：

#define maxn 100001

#define maxm 200001

#define inf 0x3f3f3f3f

int n,m,s,u,v,w;

struct node{

	int to,val;

};

bool vis[maxn];

vector<node>gragh[maxn];

int dis[maxn];

struct point{

	int id,distance;

	bool operator < (const point & a)const{//重载<，适用于结构体

		return distance>a.distance;

	}

};

priority_queue<point>q;

void dijkstra(){

	for(int i=1;i<=n;i++){

		if(i==s)continue;

		dis[i]=inf;

	}//初始化

	q.push({s,0});//把起点扔进堆

	while(!q.empty()){

		point curr=q.top();q.pop();//取出队头

		if(vis[curr.id])continue;//注意！这一句不能少，有可能堆中出现id相同但是distance不同的情况

		vis[curr.id]=1;//vis数组在这里的意思是这个点进没进过堆。

		for(int i=0;i<gragh[curr.id].size();i++){//遍历与之相连的所有点

			if(dis[gragh[curr.id][i].to]>dis[curr.id]+gragh[curr.id][i].val){//若能松弛

				dis[gragh[curr.id][i].to]=dis[curr.id]+gragh[curr.id][i].val;//松弛

				q.push({gragh[curr.id][i].to,dis[gragh[curr.id][i].to]});//把被松弛的点扔进堆，格式{点的序号，当前distance}

			}

		}

	}

}

这样优化，dijkstra就被优化到了这个复杂度：\(O(m log m)\)

对于大多数题这个复杂度稳过了。

巴特西

算法之Dijkstra及其堆优化和SPFA：图上单源最短路径神器

签到题……

SPFA算法

dijkstra算法

原始算法

堆优化

最新文章

热门文章