【模板】最短路问题系列（Dijkstra、SPFA、A*等算法）

问题描述

单源最短路径、多源最短路径。

堆优化Dijkstra

1. 核心思路：

更新等式：dis[to] = dis[pos] + edge[pos][to];
贪心优化：基本可以认为，由近到远更新答案，是一种更优的选择

2、核心操作：贪心（优先队列实现） + 松弛

3、算法流程：

step1. 优先队列中存放的是 <节点编号，起点到该节点的距离>
step2. 选取队列头部节点，如果已经用该节点更新过别人，就跳过（避免重复操作）
step3. 用该节点所连的边松弛所有去向节点，将被更新的去向节点存入队列
step4. 重复上述操作，直到队列为空

4、复杂度分析：

O(m log N) ， 比SPFA稳定。

5、 代码模板：

struct ss{
	int to,nex,va;
}edge[M];int head[N],ecnt;
priority_queue<ss>q;
int dis[N];//dis[to]=min(dis[to],dis[pos]+edge[i].va);
bool vis[N];
void dijkstra(int S){
	memset(dis,0x3f,sizeof(dis));
	q.push( (ss){S,0,0} );
	while(!q.empty()){
		int pos=q.top().to,va=q.top().va;q.pop();
		if(vis[pos]) continue;//已经用pos点更新过其他点
		vis[pos]=true;
		for(int i=head[to];i;i=edge[i].nex)
		if(dis[edge[i].to]>dis[pos]+va){
			dis[edge[i].to]=dis[pos]+va;
			q.push( (ss){ edge[i].to,0,dis[edge[i].to] } );
		}
	}
	return ;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

SPFA

1. 核心思路：

更新等式：dis[to] = dis[pos] + edge[pos][to];
贪心优化：基本可以认为，由近到远更新答案，是一种更优的选择

2、核心操作：BFS+松弛

3、复杂度分析：

玄学复杂度，就当是O(nlogn ~ n² ） 就好

4、 代码模板：

inline void spfa(int S,int T){
	q.push(S);vis[S]=true;dis[S]=0;
	while(!q.empty()){
		int pos=q.front();q.pop();vis[pos]=false;
		for(int i=head[pos];i;i=edge[i].nex)
		if(dis[edge[i].to]>dis[pos]+edge[i].va){
			dis[edge[i].to]=dis[pos]+edge[i].va;
			if(!vis[edge[i].to]){
				q.push(edge[i].to;
				vis[edge[i].to]=true;
			}
		}
	} return ;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

A*算法【待填】

之后想起来了再更