最短路径Bellman-Ford算法和SPFA算法详解

Bellman-Ford算法介绍

Bellman-Ford算法证明

Bellman-Ford算法实现

SPFA算法详解

Bellman-Ford算法介绍

Dijkstra算法可以很好的解决无负权图的最短路径问题，但是如果出现了负权边，Dijkstra算法就会失效。为了更好地求解有负权边的最短路径问题，需要使用Bellman-Ford算法（简称BF算法）。和Dijkstra算法一样，Bellman-Ford算法可以解决单源最短路径问题，但也能处理有负权边的情况

现在考虑环，也就是从某个顶点出发、经过若干个不同的顶点之后可以回到该顶点的情况。而根据环中边的边权之和的正负，可以将环分为零环、正环、负环（边权之和为0、正、负）。显然，图中的零环和正环不会影响最短路径的求解，因为零环和正环的存在不能使最短路径最短；而如果图中有负环，且从源点可以到达，那么就会影响最短路径的求解；但如果图中的负环无法从源点出发到达，则最短路径的求解不会受到影响。

与Dijkstra算法相同，Bellman-Ford算法设置一个数组d，用来存放从源点到达各个顶点的最短距离。同时Bellman-Ford算法返回一个bool值：如果其中存在从源点可达的负环，那么函数将返回false；否则，函数返回true，此时数组d中存放的值就是从源点到达各顶点的最短距离。

Bellman-Ford算法的主要思路如下面的伪代码所示。需要对图中的边进行V-1轮操作，每轮都遍历图中的所有边：对每条边u->v，如果以u为中介点可以使d[v]更小，即d[u]+length[u->v]<d[v]成立时，就用d[u]+length[u->v]更新d[v]。同时也可以看到，Bellman-Ford算法的时间复杂度是 $O\left ( VE \right )$ ，其中n是顶点个数，E是边数。

for(int i=0;i<n-1;i++){
	for(each edge u->v){
		if(d[u]+length[u->v]<d[v]){
			d[v]=d[u]+length[u->v];
		}
	}
}

此时，如果图中没有从源点可达的负环，那么数组d中的所有值都应当已经达到最优。因此，如下面的伪代码所示，只需要再对所有边进行一轮操作，判断是否有某条边u->v仍然满足d[u]+length[u->v]<d[v]，如果有，则说明图中有从源点可达的负环，返回false；否则说明数组d中的所有值都已经达到最优，返回true。

for(each edge u->v){
	if(d[u]+length[u->v]<d[v]){
		return false;
	}
	return true;
}

Bellman-Ford算法证明

首先如果最短路径存在，那么最短路径上的顶点个数肯定不会超过V个。于是，如果把源点s作为一棵树的根节点，把其他结点按照最短路径的结点顺序连接，就会生成一棵最短路径树。显然，在最短路径树中，从源点S到达其余各顶点就是原图中对应的最短路径，且原图和源点一旦确定，最短路径树也就确定了。另外，由于最短路径上的顶点个数不超过V个，因此最短路径树的层数一定不超过V。

由于初始状态下d[s]为0，因此在接下来的步骤中d[s]不会被改变（也就是说，最短路径树中第一层结点d值被确定）。接着，通过Bellman-Ford算法的第一轮操作之后，最短路径中的第二层顶点的d值也会被确定下来：然后进行第二轮操作。于是第三层顶点的d值也被确定下来。这样计算直到最后一层顶点的d值确定。由于最短路径树的层数不超过V层，因此Bellman-Ford算法的松弛操作不会超过V-1轮。证毕。

Bellman-Ford算法实现

由于Bellman-Ford算法需要遍历所有边，显然使用邻接表会比较方便：如果使用邻接矩阵，则时间复杂度会上升到 $O\left ( V^{3} \right )$ 。使用邻接表实现的代码如下：

struct node{
	int v,dis;//临界便的目标顶点，邻接边的边权 
};
vector<node> Adj[maxn];
int n;
int d[maxn];//起点到达各点的最短路径长度
bool Bellman(int s){
	fill(d,d+maxn,INF);
	d[s]=0;
	//求解数组d 
	for(int i=0;i<n-1;i++){
		for(int u=0;u<n;u++){
			for(int j=0;j<Adj[u].size();j++){
				int v=Adj[u][j].v;
				int dis=Adj[u][j].dis;
				if(d[u]+dis<d[v]){
					d[v]=d[u]+dis;
				}
			}
		}
	}
	//判断负环
	for(int u=0;u<n;u++){
		for(int j=0;j<Adj[u].size();j++){
			int v=Adj[u][j].v;
			int dis=Adj[u][j].dis;
			if(d[u]+dis<d[v]){
				return false;
			}
		}
	} 
	return true;
}

如果在某一轮操作时，发现所有边都没有被松弛，那么说明数组d中的所有值都已经达到最优，不需要再继续，提前退出即可，这样做可以稍微加一点速度。至于最短路径的求解方法、有多重标尺时做法均与Dijkstra算法中介绍的相同，此处不再重复介绍。唯一需要注意的是统计最短路径条数的做法：由于Bellman-Ford算法期间会多次访问曾经访问过的顶点，如果单纯按照Dijkstra算法中介绍的num数组的写法，将会反复累计已经计算过的顶点。为了解决这个问题，需要设置记录前驱的数组set<int>pre[maxn]，当遇到一条和已有最短路径长度相同的路径时，必须重新计算最短路径的条数。

例题

给出N个城市，M条无向边，每个城市中都有一定数目的救援小组，所有边的边权已知。现在给出起点和终点，求从起点到终点的最短路径条数及最短路径上的救援小组数目之和。如果有多条最短路径，则输出数目之和最大的。

#include<iostream>
#include<cstring>
#include<vector>
#include<set>
#include<algorithm>
using namespace std;
const int maxn=510;
const int INF=10000000000;
struct node{
	int v,dis;
	node(int _v,int _dis):v(_v),dis(_dis) {}
}; 
vector<node> Adj[maxn];
int n,m,st,ed,weight[maxn];
int d[maxn],w[maxn],num[maxn];//记录最短距离，最大点权之和，最短路径条数
set<int> pre[maxn];//前驱
void bellman(int s){
	fill(d,d+maxn,INF);
	memset(num,0,sizeof(num));
	memset(w,0,sizeof(w));
	d[s]=0;
	w[s]=weight[s];
	num[s]=1;
	for(int i=0;i<n-1;i++){
		for(int u=0;u<n;u++){
			for(int j=0;j<Adj[u].size();j++){
				int v=Adj[u][j].v;
				int dis=Adj[u][j].dis;
				if(d[u]+dis<d[v]){
					d[v]=d[u]+dis;
					w[v]=w[u]+weight[v];
					num[v]=num[u];
					pre[v].clear();
					pre[v].insert(u);
				}
				else if(d[u]+dis==d[v]){
					if(w[u]+weight[v]>w[v]){
						w[v]=w[u]+weight[v];
					}
					pre[v].insert(u);
					num[v]=0;
					set<int>::iterator it;
					for(it=pre[v].begin();it!=pre[v].end();it++){
						num[v]+=num[*it];
					}
				}
			}
		}
	}
}
int main(){
	cin>>n>>m>>st>>ed;
	for(int i=0;i<n;i++){
		cin>>weight[i];
	}
	int u,v,wt;
	for(int i=0;i<m;i++){
		cin>>u>>v>>wt;
		Adj[u].push_back(node(v,wt));
		Adj[v].push_back(node(u,wt));
	}
	bellman(st);
	cout<<num[ed]<<" "<<w[ed]<<endl;
	return 0;
}

SPFA算法详解

虽然Bellman-Ford算法的思路很简洁，但是 $O\left ( VE \right )$ 的时间复杂度确实很高，在很多情况下并不尽人意。仔细观察会发现，Bellman-Ford算法的每轮操作都需要操作所有边，显然这其中会有大量无意义的操作，严重影响了算法的性能。于是注意到，只有当某个顶点u的d[u]值改变时，从它出发的边的邻接点v的d[v]值才有可能被改变。由此可以进行一个优化：建立一个队列，每次将队首顶点u取出，然后对从u出发的所有边u->v进行松弛操作，也就是判断d[u]+length[u->v]<d[v]是否成立，如果成立，则用d[u]+length[u->v]覆盖d[v]，于是d[v]获得更优的值，此时如果v不在队列中，就把v加入队列。这样操作直到队列为空（说明图中没有从源点可达的负环），或是某个顶点的入队次数超过V-1（说明图中存在从源点可达的负环），下面是实现的伪代码：

queue<int> Q;
源点s入队
while(队列非空){
	取出队首元素u;
	for(u的所有邻接边u->v){
		if(d[u]+dis<d[v]){
			d[v]=d[u]+dis;
			if(v当前不在队列){
				v入列;
				if(v入队次数大于n-1){
					说明有可达负环，return; 
				} 
			}
		}
	} 
}

这种优化后的算法被称为SPFA算法，它的期望时间复杂度是 $O\left ( kE \right )$ ，其中E是图的边数，k是一个常数，在很多情况下k不超过2，可见这个算法在大部分数据时异常高效，并且经常性地优于堆优化的Dijkstra算法。但如果图中有从源点可达的负环，传统SPFA的时间复杂度会退化为 $O\left ( VE \right )$ 。理解SPFA的关键是理解它是如何从Bellman-Ford算法优化得来的。

下面给出邻接表表示的图的SPFA代码。如果事先知道图中不会有环，那么num数组的部分可以去掉。注意：使用SPFA可以判断是否存在从源点可达的负环，如果负环从源点不可达，则需要添加一个辅助顶点C，并添加一条从源点到达C的有向边以及V-1条从C到达除源点外各顶点的有向边才能判断负环是否存在。

vector<node> Adj[maxn];
int n,d[maxn],num[maxn];//num[maxn]记录入队次数
bool inq[maxn];
bool SPFA(int s){
	memset(inq,false,sizeof(inq));
	memset(num,0,sizeof(num));
	fill(d,d+maxn,INF);
	queue<int>Q;
	Q.push(s);
	inq[s]=true;
	num[s]++;
	d[s]=0;
	while(!Q.empty()){
		int u=Q.front();
		Q.pop();
		inq[u]=false;
		for(int j=0;j<Adj[u].size();j++){
			int v=Adj[u][j].v;
			int dis=Adj[u][j].dis;
			if(d[u]+dis<d[v]){
				d[v]=d[u]+dis;
				if(!inq[v]){
					Q.push(v);
					inq[v]=true;
					num[v]++;
					if(num[v]>=n){
						return false;
					}
				}
			}
		}
	}
	return true;
}

SPFA算法十分灵活，其内部的写法可以根据具体场景的不同进行调整。