最短路径算法之四——SPFA算法

SPAF算法

求单源最短路的SPFA算法的全称是:Shortest Path Faster Algorithm,该算法是西南交通大学段凡丁于1994年发表的。

它可以在O(kE)的时间复杂度内求出源点到其他所有点的最短路径。

其中k为所有顶点进队的平均次数,可以证明k一般小于等于2,可以处理负边,但无法处理带负环的图(负环和负边不是一个概念)。

SPFA的实现甚至比Dijkstra或者Bellman_Ford还要简单。

SPFA算法过程:
  我们记源点为S,由源点到达点i的“当前最短路径”为D[i],开始时将所有D[i]初始化为无穷大,D[S]则初始化为0。算法所要做的,就是在运行过程中,不断尝试减小D[]数组的元素,最终将其中  每一个元素减小到实际的最短路径。
  过程中,我们要维护一个队列,开始时将源点置于队首,然后反复进行这样的操作,直到队列为空:
  (1)从队首取出一个结点u,扫描所有由u结点可以一步到达的结点,具体的扫描过程,随存储方式的不同而不同;
  (2)一旦发现有这样一个结点,记为v,满足D[v] > D[u] + w(u, v),则将D[v]的值减小,减小到和D[u] + w(u, v)相等。其中,w(u, v)为图中的边u-v的长度,由于u-v必相邻,所以这个长度一定已知(不然我们得到的也不叫一个完整的图);这种操作叫做松弛。
  (3)上一步中,我们认为我们“改进了”结点v的最短路径,结点v的当前路径长度D[v]相比于以前减小了一些,于是,与v相连的一些结点的路径长度可能会相应地减小。注意,是可能,而不是一定。但即使如此,我们仍然要将v加入到队列中等待处理,以保证这些结点的路径值在算法结束时被降至最优。

判断有无负环:
  如果某个点进入队列的次数超过N次则存在负环(SPFA无法处理带负环的图)
  对于不存在负权回路的图来说,上述算法是一定会结束的。因为算法在反复优化各个最短路径长度,总有一个时刻会进入“无法再优化”的局面,此时一旦队列读空,算法就结束了。然而,如果图中存  在一条权值为负的回路,就糟糕了,算法会在其上反复运行(因为d[]加上一个负数肯定变下了,所以在有负环的情况下,会不断有数进入队列),通过“绕圈”来无休止地试图减小某些相关点的最短路  径值。假如我们不能保证图中没有负权回路,一种“结束条件”是必要的。这种结束条件是什么呢?
  思考Bellman-Ford算法,它是如何结束的?显然,最朴素的Bellman-Ford算法不管循环过程中发生了什么,一概要循环|V|-1遍才肯结束。凭直觉我们可以感到,SPFA算法“更聪明一些”,就是说我  们可以猜测,假如在SPFA中,一个点进入队列——或者说一个点被处理——超过了|V|次,那么就可以断定图中存在负权回路了。

SPFA代码实现(以HDU1535为例):

 #include<stdio.h>
#include<limits.h>
#include<iostream>
#include<string>
#include<queue>
#define MAXN 1000000
using namespace std;
struct e
{
int begin;
int end;
int dis;
} edge1[MAXN+],edge2[MAXN+];
int dis[MAXN+],first[MAXN+];
bool vis[MAXN+];
int T,S,D,N,k,M;
void SPFA(int begin,struct e edge[])
{
for (int i=; i<=N; i++)
{
dis[i]=INT_MAX;
vis[i]=;
}
queue <int> Q;
Q.push(begin);
dis[begin]=;
while (!Q.empty())
{
begin=Q.front();
Q.pop();
vis[begin]=;
for (int i=first[begin]; edge[i].begin==begin; i++)
if (dis[edge[i].end]>dis[begin]+edge[i].dis)
{
dis[edge[i].end]=dis[begin]+edge[i].dis;
if (!vis[edge[i].end])
{
Q.push(edge[i].end);
vis[edge[i].end]=;
}
}
}
}
void init(struct e edge[])
{
memset(first,,sizeof(first));
first[edge[].begin]=;
for (int i=; i<=M; i++)
if (edge[i-].begin!=edge[i].begin) first[edge[i].begin]=i;
}
bool cmp(struct e a,struct e b)
{
return a.begin<b.begin;
}
int main()
{
int T;
cin>>T;
while (T--)
{
scanf("%d %d",&N,&M);
int x1,x2,x3;
for (int i=; i<=M; i++)
{
scanf("%d %d %d",&x1,&x2,&x3);
edge1[i].begin=x1,edge1[i].end=x2,edge1[i].dis=x3;
edge2[i].begin=x2,edge2[i].end=x1,edge2[i].dis=x3;
}
sort(edge1+,edge1+M+,cmp);
sort(edge2+,edge2+M+,cmp);
init(edge1);
SPFA(,edge1);
int cnt=;
for (int i=; i<=N; i++)
cnt+=dis[i];
init(edge2);
SPFA(,edge2);
for (int i=; i<=N; i++)
cnt+=dis[i];
printf("%d\n",cnt);
}
return ;
}

  期望的时间复杂度:O(ke), 其中k为所有顶点进队的平均次数,可以证明k一般小于等于2。

上一篇:ScrollView中嵌套GridView,ListView只显示一行的解决办法


下一篇:CentOS 7 之几个新特性(转)