spfa算法

编程与算法

spfa算是是使用队列去优化bellman的一种算法吧。

求单源最短路的SPFA算法的全称是：Shortest Path Faster Algorithm，是西南交通大学段凡丁于1994年发表的。从名字我们就可以看出，这种算法在效率上一定有过人之处。很多时候，给定的图存在负权边，这时类似Dijkstra等算法便没有了用武之地，而Bellman-Ford算法的复杂度又过高，SPFA算法便派上用场了。简洁起见，我们约定加权有向图G不存在负权回路，即最短路径一定存在。如果某个点进入队列的次数超过N次则存在负环（SPFA无法处理带负环的图）。当然，我们可以在执行该算法前做一次拓扑排序，以判断是否存在负权回路，但这不是我们讨论的重点。我们用数组d记录每个结点的最短路径估计值，而且用邻接表来存储图G。我们采取的方法是动态逼近法：设立一个先进先出的队列用来保存待优化的结点，优化时每次取出队首结点u，并且用u点当前的最短路径估计值对离开u点所指向的结点v进行松弛操作，如果v点的最短路径估计值有所调整，且v点不在当前的队列中，就将v点放入队尾。这样不断从队列中取出结点来进行松弛操作，直至队列空为止。定理: 只要最短路径存在，上述SPFA算法必定能求出最小值。

算法简介

  • 建立一个带权值的邻接矩阵，然后定义dis[N]表示源点到其他点的距离，然后将源点入队。
  • 当队列不空时：取出队列中第一个元素，遍历它的出度edge，如果以该有向边edge为中间边到达某个节点的距离小于原本的距离(dis[x] + edge < dis[y])，则将这个点y入队，同时进行松弛操作。
  • 当一个点入队超过n次时，表明他经过了n次松弛操作。说明存在负环。

代码示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
struct Edge{
	int wi;		//权值
	int to;		//边终点
};
int V_NUM;				//节点数
int E_NUM;				//边数
vector <Edge> v[M];		//邻接表式
int dis[M];				//到i点的距离
int times[M];			//i点入队的次数
int is_push[M];			//i点是否入队

bool spfa(int st){
	int i;
	queue <int> qu;
	for (int i = 0; i < V_NUM; ++i){
		if(i==st)dis[i] = 0;
		else dis[i] = VMAX;
		times[i] = 0;
		is_push[i] = 0;
	}
	qu.push(st);
	times[st] = 1;
	is_push[st] = 1;
	while(!qu.empty()){
		int temp_v = qu.front();
		int n_vi = (int)v[temp_v].size();		//该点的出度
		for(i=0;i<n_vi;i++){
			Edge *e = &v[temp_v][i];			//取出一条边
			if(dis[e->to]>(dis[temp_v]+e->wi)){	//满足松弛条件
				dis[e->to] = dis[temp_v]+e->wi;
				qu.push(e->to);
				times[e->to]++;
				is_push[e->to] = 1;
				if(times[e->to]>V_NUM){			//入队次数爆表，存在负环
					while(!qu.empty())qu.pop();
					return 0;
				}
			}
		}
		qu.pop();
		is_push[temp_v] = 0;
	}
	return 1;
}

再次补充

虽然介绍越来越短了，但是相信大家，看到代码后还是可以自己看懂的哈。