Dijkstra & SPFA

两个图论最短路算法板子

• $Dijkstra$和$SPFA$（优化$Bellman-Ford$）的板子+优化+个人理解
• 弱化版 单源最短路径 可$SPFA$
• 标准版 单源最短路径 不可$SPFA$

---

$SPFA$（优化$Bellman-Ford$）

至于$Bellman-Ford$这里就不提了，毕竟已经淘汰了（复杂度满了$O(nm)$）

算法

大致思路：利用队列$bfs$优化$Bellman-Ford$，从当前点（第一次就是起点）开始，遍历每一个出边，更新到这条边终点的最短路径（如果可以更新的话），如果这个点未标记过，则把这个终点push进队列，并标记（表明更新过），之后每次从队首取出元素并将其置为未标记（目的是可重复更新），对当前点重复上述步骤即可得出答案

核心点：

• 每次取出队首元素后一定要去标记
• “可重复更新”是该算法的核心
• 复杂度为$O(ke)$，$k$是个常数（通常等于2左右），然而会有毒瘤题卡$SPFA$，使其复杂度达到满的$O(nm)$，因而在不含负权图中尽量使用$Dijkstra$

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf=2147483647;

struct Edge{ //边结构体
	int u,v,w,next;
}e[1000005];

int n,m,s,ans,cnt,vis[1000005],head[1000005];
inline void addedge(int u,int v,int w){ //前向星加边
	e[++cnt].u=u;
	e[cnt].v=v;
	e[cnt].w=w;
	e[cnt].next=head[u];
	head[u]=cnt;
}
int dis[1000005];
inline void SPFA(){ //核心
	for(int i=1;i<=n;i++){ //最短路初始化为inf
		dis[i]=inf;
	}
	queue<int> q; //存入每个点的队列
	q.push(s); //起点入队
	dis[s]=0; //到起点的最短路为0
	vis[s]=1; //起点标记过
	while(!q.empty()){ //bfs
		int u=q.front(); 
		q.pop();
		vis[u]=0; //很重要，去标记，表明可以重复更新
		for(int i=head[u];i;i=e[i].next){ //遍历相连的每下一条边
			int v=e[i].v,w=d[i].w;
			if(dis[v]>dis[u]+w){ //如果满足更新条件
				dis[v]=dis[u]+w; //更新最短路
				if(vis[v]==0){ //如果没有标记过
					vis[v]=1; //则标记，表明更新了
					q.push(v); //并入队
				}
			}
		}
	}
}

int main(){
	cin>>n>>m>>s;
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		addedge(u,v,w);
	}
	SPFA();
	for(int i=1;i<=n;i++){
		cout<<dis[i]<<" ";
	}
	return 0;
}

$Dijkstra$

算法

大致思路：同$SPFA$的操作，但不同的是：思路类似于$Prim$算法，并不用重复更新某一个点，而是采用每次更新答案之前通过一顿循环，把当前情况下的到起点的最短路所对应的节点取出来，对这个节点的所有出边遍历并更新答案，然后重复上述过程，直到所有点都完成更新，复杂度是$O(n^2)$，显然不够给力，因此通常我们会采取堆优化

堆优化：由于每次需要去除当前情况下的最短路对应的节点，我们可以利用小根堆的特点，每次取出最小元素所需复杂度为$O(logn)$，因此算法的复杂度可以优化为$O((n+m)logn)$

核心点：

• 每次更新答案前取出当前情况下最短路径所对应的的节点，以此更新
• 大部分情况下不会被卡，十分好用

代码（堆优化）

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf = 2147483647;
struct Edge{ 
	int u,v,w,next;
}e[1000005];

struct node{ //采用堆优化，需要开一个结构体存入终点边和对应的最短路
	int u,dis;
	bool operator <(const node&rhs)const{ //重载小于号，因为要用小根堆
		return dis>rhs.dis;
	}
};

int n,m,s,ans,cnt,now,head[1000005],dis[1000005]; //dis是答案数组
inline void addedge(int u,int v,int w){ //加边
	e[++cnt].u=u;
	e[cnt].v=v;
	e[cnt].w=w;
	e[cnt].next=head[u];
	head[u]=cnt;
}

inline void dijkstra(){
	for(int i=1;i<=n;i++) dis[i]=inf; //初始化
	priority_queue<node> q; //开小根堆
	dis[s]=0; //到起点的最短路为0
	q.push((node){s,0}); //把起点push进去
	while(!q.empty()){ //bfs
		node q1=q.top(); //取出队首的点（当前情况最短路对应的点）
		q.pop();
		int u=q1.u;
        
        //这一步很重要，比较难理解
        //因为有可能 这一次更新的点（点，最短路）入了队（先入队），
        //但是下一次又更新了一次（还是这个点，新的最短路）（后入队）
        //如果出现了
        //先入队的这个点的最短路 大于 最新情况下（即最后一次入队）时的最短路
        //那么就说明这次这个已经不是最短路了
        //就可以舍弃了，因此continue
		if(q1.dis>dis[u]) continue; 
        
		for(int i=head[u];i;i=e[i].next){ //遍历每一个出边
			int v=e[i].v,w=e[i].w;
			if(dis[v]>dis[u]+w){ //如果满足最短路要求
				dis[v]=dis[u]+w; //更新答案
				q.push((node){v,dis[v]}); //把（点，最短路）push进堆
			}
		}
	}
}

int main(){
	cin>>n>>m>>s;
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		addedge(u,v,w);
	}
	dijkstra();
	for(int i=1;i<=n;i++){
		cout<<dis[i]<<" ";
	}
	return 0;
}