单源最短路径问题（详解，bellman_ford&SPFA），附queue用法

## bellman_ford算法，朴素贪心

其原理为连续进行松弛，在每次松弛时把每条边都更新一下，若在n-1次松弛后还能更新，则说明图中有负环，因此无法得出结果，否则就完成。

### 贪心思路、描述性证明

首先指出，图的任意一条最短路径既不能包含负权回路，也不会包含正权回路，因此它最多包含|v|-1条边。

其次，从源点s可达的所有顶点如果存在最短路径，则这些最短路径构成一个以s为根的最短路径树。Bellman-Ford算法的迭代松弛操作，实际上就是按每个点实际的最短路径（虽然我们还不知道，但它一定存在）的层次，逐层生成这棵最短路径树的过程。

注意，每一次遍历，都可以从前一次遍历的基础上，找到此次遍历的部分点的单源最短路径。如：这是第i次遍历，那么，通过数学归纳法，若前面单源最短路径层次为1~（i-1）的点全部已经得到，而单源最短路径层次为i的点，必定可由单源最短路径层次为i-1的点集得到，从而在下一次遍历中充当前一次的点集，如此往复迭代，[v]-1次后，若无负权回路，则我们已经达到了所需的目的--得到每个点的单源最短路径。（注意：这棵树的每一次更新，可以将其中的某一个子树接到另一个点下）

反之，可证，若存在负权回路，第[v]次遍历一定存在更新，因为负权回路的环中，必定存在一个“断点”，可用数学手段证明。

最后，我们在第[v]次更新中若没有新的松弛，则输出结果，若依然存在松弛，则表示无解。同时，我们还可以通过“断点”找到负权回路。

### 适用范围

1.单源最短路径(从源点s到其它所有顶点v);

2.有向图&无向图(无向图可以看作(u,v),(v,u)同属于边集E的有向图);

3.边权可正可负(如有负权回路输出错误提示)。

### 标程

```cpp
#include<bits/stdc++.h>
#define maxn 0x3f3f3f3f
using namespace std;
int n,m,s;
struct edge{
	int u,v,cost;
}e[1000];
int dis[1000],pre[1000];//pre为路径前驱数组
bool bellman_ford(){
	for(int i=1;i<=n;i++)dis[i]=(i==s?0:maxn);//初始化
	for(int i=1;i<n;i++)//逐点更新，最多更新n-1次
		for(int j=1;j<=m;j++)//逐边更新
		if(dis[e[j].v ]>dis[e[j].u ]+e[j].cost ){
			dis[e[j].v ]=dis[e[j].u ]+e[j].cost ;
			pre[e[j].v ]=e[j].u ;//路径前驱
		}
	bool flag=1;
	for(int i=1;i<=m;i++)
		if(dis[e[i].v ]>dis[e[i].u ]+e[i].cost ){
			flag=0;
			break;
		}//若经过n-1次松弛后仍可松弛，则存在负权边，最短路无解
	return flag;
}
void print_path(int root){
	while(root!=pre[root]){
		printf("%d<--",root);
		root=pre[root];
	}
	if(root==pre[root])printf("%d\n",root);//输出路径
}
int main(){
	scanf("%d%d%d",&n,&m,&s);
	pre[s]=s;
	for(int i=1;i<=m;i++)
		scanf("%d%d%d",&e[i].u ,&e[i].v ,&e[i].cost );
	if(bellman_ford())
		for(int i=1;i<=n;i++){
			printf("  %d\t",dis[i]);
			print_path(i);
		}
	else printf("No Solution.\n");
	return 0;
}
```
## SPFA算法

### 算法描述

用数组dis记录每个结点的最短路径估计值，而且用邻接表来存储图G。我们采取的方法是动态逼近法：设立一个先进先出的队列用来保存待优化的结点，优化时每次取出队首结点u，并且用u点当前的最短路径估计值对离开u点所指向的结点v进行松弛操作，如果v点的最短路径估计值有所调整，且v点不在当前的队列中，就将v点放入队尾。这样不断从队列中取出结点来进行松弛操作，直至队列空为止。

### 正确性证明

定理：只要最短路径存在，上述SPFA算法必定能求出最小值。

证明：每次将点放入队尾，都是经过松弛操作达到的。换言之，每次的优化将会有某个点v的最短路径估计值dis[v]变小。所以算法的执行会使d越来越小。由于我们假定图中不存在负权回路，所以每个结点都有最短路径值。因此，算法不会无限执行下去，随着dis值的逐渐变小，直到到达最短路径值时，算法结束这时的最短路径估计值就是对应结点的最短路径值。

### 主要有三个具体操作的步骤：
1.取队首元素。

2.以队首元素为起点，更新其他点（亦即松弛操作）；在这一步中，一是更新最短路径，二是加入在队列中还没有的元素到队列末尾。

3.使队首元素离开更新队列**勿忘*

### 优化

SPFA算法有两个优化策略SLF和LLL。

#### SLF：Small Label First 策略

设要加入的节点是j，队首元素为i，若dist(j)<dist(i)，则将j插入队首，否则插入队尾；

#### LLL：Large Label Last 策略

设队首元素为i，队列中所有dist值的平均值为x，若dist(i)>x则将i插入到队尾，查找下一元素，直到找到某一i使得dist(i)<=x，则将i出队进行松弛操作。

SLF 和 LLF 在随机数据上表现优秀，但是在正权图上最坏情况为 O(VE)，在负权图上最坏情况为达到指数级复杂度。

```cpp
#include<bits/stdc++.h>
#define inf 2147483647
#define maxn 100001
using namespace std;
int n,m,s;
int head[maxn];
int num;
queue<int >q;
bool check[maxn];
int dis[maxn];
struct edge{
	int u,v,w,next;
}e[maxn*5];
void add(int u,int v,int w){
	num+=1;
	e[num].u =u;
	e[num].v =v;
	e[num].w =w;
	e[num].next =head[u];
	head[u]=num;
}
void init(){
	for(int i=1;i<=n;i++)dis[i]=(i==s?0:inf);
	memset(check,false,sizeof(check));
}//初始化 
void spfa(){
	check[s]=true;
	q.push(s);//入列最尾端
	while(!q.empty()){
		int u=q.front();
		for(int k=head[u];k;k=e[k].next ){
			int v=e[k].v ,w=e[k].w ;
			if(dis[v]>dis[u]+w){
				dis[v]=dis[u]+w;
				if(!check[v]){
					check[v]=true;
					q.push(v);//入列最尾端
				}
			}
		}
		q.pop();//队首元素出列
		check[u]=false;
	}
}
int main(){
	scanf("%d%d%d",&n,&m,&s);
	init();
	int u,v,w;
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&u,&v,&w);
		add(u,v,w);
	}
	spfa();
	for(int i=1;i<=n;i++)
		printf("%d ",dis[i]);
	printf("\n");
	return 0;
}
```
## 附c++中queue的用法

入队，如例：q.push(x); 将x 接到队列的末端。

出队，如例：q.pop(); 弹出队列的第一个元素，注意，并不会返回被弹出元素的值。

访问队首元素，如例：q.front()，即最早被压入队列的元素。

访问队尾元素，如例：q.back()，即最后被压入队列的元素。

判断队列空，如例：q.empty()，当队列空时，返回true。

正在渲染内容...