频道栏目
首页 > 程序开发 > 软件开发 > 其他 > 正文
SPFA算法
2016-11-05 10:02:21         来源:amazingcode的博客  
收藏   我要投稿

SPFA(Shortest Path Faster Algorithm)(队列优化)算法是求单源最短路径的一种算法,它还有一个重要的功能是判负环(在差分约束系统中会得以体现),在Bellman-ford算法的基础上加上一个队列优化,减少了冗余的松弛操作,是一种高效的最短路算法。

简洁起见,我们约定有向加权图G不存在负权回路,即最短路径一定存在。当然,我们可以在执行该算法前做一次拓扑排序,以判断是否存在负权回路,但这不是我们讨论的重点。
我们用数组d记录每个结点的最短路径估计值,而且用邻接表来存储图G。我们采取的方法是动态逼近法:设立一个先进先出的队列用来保存待优化的结点,优化时每次取出队首结点u,并且用u点当前的最短路径估计值对离开u点所指向的结点v进行松弛操作,如果v点的最短路径估计值有所调整,且v点不在当前的队列中,就将v点放入队尾。这样不断从队列中取出结点来进行松弛操作,直至队列空为止。
定理: 只要最短路径存在,上述SPFA算法必定能求出最小值。
证明:每次将点放入队尾,都是经过松弛操作达到的。换言之,每次的优化将会有某个点v的最短路径估计值d[v]变小。所以算法的执行会使d越来越小。由于我们假定图中不存在负权回路,所以每个结点都有最短路径值。因此,算法不会无限执行下去,随着d值的逐渐变小,直到到达最短路径值时,算法结束,这时的最短路径估计值就是对应结点的最短路径值。(证毕)
期望的时间复杂度O(ke), 其中k为所有顶点进队的平均次数,可以证明k一般小于等于2。
实现方法:建立一个队列,初始时队列里只有起始点,在建立一个表格记录起始点到所有点的最短路径(该表格的初始值要赋为极大值,该点到他本身的路径赋为0)。然后执行松弛操作,用队列里有的点去刷新起始点到所有点的最短路,如果刷新成功且被刷新点不在队列中则把该点加入到队列最后。重复执行直到队列为空

判断有无负环:如果某个点进入队列的次数超过N次则存在负环(SPFA无法处理带负环的图)

\

判断有无负环:如果某个点进入队列的次数超过N次则存在负环(SPFA无法处理带负环的图)

\

首先源点a入队,当队列非空时:
1、队首元素(a)出队,对以a为起始点的所有边的终点依次进行松弛操作(此处有b,c,d三个点),此时路径表格状态为:

\

在松弛时三个点的最短路径估值变小了,而这些点队列中都没有出现,这些点
需要入队,此时,队列中新入队了三个结点b,c,d
队首元素b点出队,对以b为起始点的所有边的终点依次进行松弛操作(此处只有e点),此时路径表格状态为:

\

在最短路径表中,e的最短路径估值也变小了,e在队列中不存在,因此e也要
入队,此时队列中的元素为c,d,e
队首元素c点出队,对以c为起始点的所有边的终点依次进行松弛操作(此处有e,f两个点),此时路径表格状态为:

\

在最短路径表中,e,f的最短路径估值变小了,e在队列中存在,f不存在。因此
e不用入队了,f要入队,此时队列中的元素为d,e,f
队首元素d点出队,对以d为起始点的所有边的终点依次进行松弛操作(此处只有g这个点),此时路径表格状态为:

\

在最短路径表中,g的最短路径估值没有变小(松弛不成功),没有新结点入队,队列中元素为f,g
队首元素f点出队,对以f为起始点的所有边的终点依次进行松弛操作(此处有d,e,g三个点),此时路径表格状态为:

\

在最短路径表中,e,g的最短路径估值又变小,队列中无e点,e入队,队列中存在g这个点,g不用入队,此时队列中元素为g,e
队首元素g点出队,对以g为起始点的所有边的终点依次进行松弛操作(此处只有b点),此时路径表格状态为:

\

在最短路径表中,b的最短路径估值又变小,队列中无b点,b入队,此时队列中元素为e,b
队首元素e点出队,对以e为起始点的所有边的终点依次进行松弛操作(此处只有g这个点),此时路径表格状态为:

\

在最短路径表中,g的最短路径估值没变化(松弛不成功),此时队列中元素为b
队首元素b点出队,对以b为起始点的所有边的终点依次进行松弛操作(此处只有e这个点),
此时路径表格状态为:

\

在最短路径表中,e的最短路径估值没变化(松弛不成功),此时队列为空了
最终a到g的最短路径为14

实现代码如下

 

#include 
#include 
#include 
using namespace std;
const int N = 105;
const int INF = 99999999;
int map[N][N], dist[N];
bool visit[N];
int n, m;
void init() {//初始化
	int i, j;
	for (i = 1; i < N; i++) {
		for (j = 1; j < N; j++) {
			if (i == j) {
				map[i][j] = 0;
			} else {
				map[i][j] = map[j][i] = INF;}
		}
	}
}
void spfa(int start) {
	queue Q;
	int i, now;
	memset(visit, false, sizeof(visit));
	for (i = 1; i <= n; i++){
		dist[i] = INF;
	}
	dist[start] = 0;
	Q.push(start);
	visit[start] = true;
	while (!Q.empty()) {
		now = Q.front();
		Q.pop();
		visit[now] = false;
		for (i = 1; i <= n; i++) {
			if (dist[i] > dist[now] + map[now][i]) {
				dist[i] = dist[now] + map[now][i];
				if (visit[i] == 0) {
					Q.push(i);
					visit[i] = true;}}}
	}}
int main(){
	while(scanf("%d%d",&n,&m)!=EOF){
		init();
		while(m--){
			int a,b,c;
			scanf("%d%d%d",&a,&b,&c);
			if(map[a][b] > c){
				map[a][b] = map[b][a] = c;
			}
		}
		spfa(1);
		printf("%d\n",dist[n]);
	}
	return 0;
}
点击复制链接 与好友分享!回本站首页
相关TAG标签 算法
上一篇:Yar异步调用的超时时间问题以及解决方案
下一篇:【数据结构】哈希表
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站