SPFA算法 弗洛伊德算法

介绍:

单源最短路径的算法最常用的是Dijkstra,些算法从时间复杂度来说为O(n^2),但是面对含有负权植的图来说就无能为力了,此时Dellman-ford算法就有用了,这咱算法是采用的是动态规化的思想,但是1994年西南交通大学段凡丁发表了SPFA(ShortestPath FasterAlgorithm)听这个名字就懂了,这种算法在时间上一定很快了。它是对Dellman-ford的优化,所以建议今后直接学SPFA。很多时候,给定的图存在负权边,这时类似Dijkstra等算法便没有了用武之地,而Bellman-Ford算法的复杂度又过高,SPFA算法便派上用场了。

思路:
简洁起见,我们约定有向加权图G不存在负权回路,即最短路径一定存在。当然,我们可以在执行该算法前做一次拓扑排序,以判断是否存在负权回路,但这不是我们讨论的重点。
和上文一样,我们用数组d记录每个结点的最短路径估计值,而且用邻接表来存储图G。我们采取的方法是动态逼近法:设立一个先进先出的队列用来保存待优化的结点,优化时每次取出队首结点u,并且用u点当前的最短路径估计值对离开u点所指向的结点v进行松弛操作,如果v点的最短路径估计值有所调整,且v点不在当前的队列中,就将v点放入队尾。这样不断从队列中取出结点来进行松弛操作,直至队列空为止。
定理3只要最短路径存在,上述SPFA算法必定能求出最小值。
证明:每次将点放入队尾,都是经过松弛操作达到的。换言之,每次的优化将会有某个点v的最短路径估计值d[v]变小。所以算法的执行会使d越来越小。由于我们假定图中不存在负权回路,所以每个结点都有最短路径值。因此,算法不会无限执行下去,随着d值的逐渐变小,直到到达最短路径值时,算法结束,这时的最短路径估计值就是对应结点的最短路径值。(证毕)
刚才我们只是笼统地说SPFA算法在效率上有过人之处,那么到底它的复杂度是怎样的?
定理4在平均情况下,SPFA算法的期望时间复杂度为O(E)。
证明:上述算法每次取出队首结点u,并访问u的所有临结点的复杂度为O(d),其中d为点u的出度。运用均摊分析的思想,对于|V|个点|E|条边的图,点的平均出度为,所以每处理一个点的复杂度为O()。假设结点入队的次数h,显然h随图的不同而不同。但它仅与边的权值分布有关。我们设h=kV,则算法SPFA的时间复杂度为。在平均的情况下,可以将k看成一个比较小的常数,所以SPFA算法在一般情况下的时间复杂度为O(E)。(证毕)
聪明的读者一定发现了,SPFA和经过简单优化的Bellman-Ford无论在思想上还是在复杂度上都有相似之处。确实如此。两者的思想都属于标号修正的范畴。算法是迭代式的,最短路径的估计值都是临时的。算法思想是不断地逼近最优解,只在最后一步才确定想要的结果。但是他们实现的方式上存在差异。正因为如此,它们的时间复杂度其实有较大差异的。在Bellman-Ford算法中,要是某个点的最短路径估计值更新了,那么我们必须对所有边指向的终点再做一次松弛操作;在SPFA算法中,某个点的最短路径估计值更新,只有以该点为起点的边指向的终点需要再做一次松弛操作。在极端情况下,后者的效率将是前者的n倍,一般情况下,后者的效率也比前者高出不少。基于两者在思想上的相似,可以这样说,SPFA算法其实是Bellman-Ford算法的一个进一步优化的版本。

算法流程

算法大致流程是用一个队列来进行维护。初始时将源加入队列。每次从队列中取出一个元素,并对所有与他相邻的点进行松弛,若某个相邻的点松弛成功,则将其入队。直到队列为空时算法结束。

这个算法,简单的说就是队列优化的bellman-ford,利用了每个点不会更新次数太多的特点发明的此算法

SPFA——Shortest Path FasterAlgorithm,它可以在O(kE)的时间复杂度内求出源点到其他所有点的最短路径,可以处理负边。SPFA的实现甚至比Dijkstra或者Bellman_Ford还要简单:

设Dist代表S到I点的当前最短距离,Fa代表S到I的当前最短路径中I点之前的一个点的编号。开始时Dist全部为+∞,只有Dist[S]=0,Fa全部为0。

维护一个队列,里面存放所有需要进行迭代的点。初始时队列中只有一个点S。用一个布尔数组记录每个点是否处在队列中。

每次迭代,取出队头的点v,依次枚举从v出发的边v->u,设边的长度为len,判断Dist[v]+len是否小于Dist[u],若小于则改进Dist[u],将Fa[u]记为v,并且由于S到u的最短距离变小了,有可能u可以改进其它的点,所以若u不在队列中,就将它放入队尾。这样一直迭代下去直到队列变空,也就是S到所有的最短距离都确定下来,结束算法。若一个点入队次数超过n,则有负权环

SPFA在形式上和宽度优先搜索非常类似,不同的是宽度优先搜索中一个点出了队列就不可能重新进入队列,但是SPFA中一个点可能在出队列之后再次被放入队列,也就是一个点改进过其它的点之后,过了一段时间可能本身被改进,于是再次用来改进其它的点,这样反复迭代下去。设一个点用来作为迭代点对其它点进行改进的平均次数为k,有办法证明对于通常的情况,k在2左右。

代码:

存图的方式我是利用链式向前星的方式存图的,下面是代码:

#include
#include
#include
#define Maxn 100
#define Maxm 10000
#define Max 10000

intused[Maxn],outqueue[Maxn],head[Maxn],queue[Maxn],low[Maxn],n,m;

struct Edge
{
int to,w,next;
}edge[Maxm];

bool SPFA(int start)
{
int i =0, iq = 0;
used[start] = 1;
queue[iq++] = start;
low[start] = 0;
while (i != iq)
{
int top = queue[i];
used[top] = 0;
outqueue[top]++;//用来判断是否有环路
if (outqueue[top] > n) return false;
for (int k = head[top]; k != -1; k = edge[k].next)//宽搜每条边
{
if (low[edge[k].to] > low[top] + edge[k].w)//对点进行松驰
low[edge[k].to] = low[top] + edge[k].w;
if (!used[edge[k].to])
{
used[edge[k].to] = 1;
queue[iq++] = edge[k].to;
}
}
i++;
}
return true;
}

int main()
{
while (scanf("%d%d", &n ,&m) != EOF)
{
memset (used, 0 ,sizeof(used));
memset (head, -1 ,sizeof(head));
memset (outqueue, 0 ,sizeof(outqueue));
memset (low, Max, sizeof(low));
int k = 0;
while (m--)
{
int a,b,w;
scanf ("%d%d%d", &a, &b, &w);
edge[k].to = b;
edge[k].w = w;
edge[k].next = head[a];
head[a] = k++;
}
if (SPFA(1))
printf ("%dn", low[n]);
else
printf ("不存在最短n");
}
}

刚才那个代码是最短路里面效率最高的,为了提高效率,队列那个是自己写的,而不是调用stl里面的,但是看起来比较难,很难读懂,下面是用stl里面的queue写的。

#include
#include
#include
#include
#define Maxn 100
#define Maxm 10000
#define Max 10000
using namespace std;

intused[Maxn],outqueue[Maxn],head[Maxn],low[Maxn],n,m;

struct Edge
{
int to,w,next;
}edge[Maxm];

bool SPFA (int start)
{
queue a;
used[start] = 1;
low[start] = 0;
a.push(start);
while (!a.empty())
{
int top = a.front();
a.pop();
outqueue[top]++;
if (outqueue[top] > n) return false;
for (int k = head[top]; k!= -1; k = edge[k].next)
{
if (low[edge[k].to] > low[top] + edge[k].w)
low[edge[k].to] = low[top] + edge[k].w;
if (!used[edge[k].to])
{
used[edge[k].to] = 1;
a.push(edge[k].to);
}
}
SPFA算法 弗洛伊德算法
}
return true;
}

int main()
{
while (scanf("%d%d", &n ,&m) != EOF)
{
memset (used, 0 ,sizeof(used));
memset (head, -1 ,sizeof(head));
memset (outqueue, 0 ,sizeof(outqueue));
memset (low, Max, sizeof(low));
int k = 0;
while (m--)
{
int a,b,w;
scanf ("%d%d%d", &a, &b, &w);
edge[k].to = b;
edge[k].w = w;
edge[k].next = head[a];
head[a] = k++;
}
if (SPFA(1))
printf ("%dn", low[n]);
else
printf ("不存在最短n");
}
}

  

爱华网本文地址 » http://www.413yy.cn/a/25101018/372758.html

更多阅读

弗洛伊德力比多理论解析自我(精神分析学) 弗洛伊德梦的解析

英文叫libido,力比多客体,在概念上讲,应该都是一样的。指那些在性方面能引起心理活动的事物,意识,观念。或指能使人倾注原欲于之的事物,意识,观念。等等。用弗洛伊德精神分析理论分析的中国现当代文学作品,太多了,基本上每一个文学文本都可进

心理悬疑小说:弗洛伊德禁地

心理悬疑小说:弗洛伊德禁地[总目录]神秘惊悚的心理克隆计划,带出一段残酷的寻父旅程,解开所有密码的孩子,却是被父亲遗弃的实验品,当人性和欲望纠缠在一起,死亡和遗忘让一切回归起点。男孩的父亲,连同汽车在空旷的雪地上平空消失;女孩的父亲

英国卢西恩·弗洛伊德油画作品 弗洛伊德油画

卢西恩。佛洛伊德生于1922年,是著名心理学家西蒙。佛洛伊德的孙子。和所有的维也纳人一样,他与生俱来的怀疑、孤独和好奇精神常常使自己不安,对世界的感知也就保持了一种特殊的知觉能力。1933年他移居英国并成为画家后,这种知觉能力也就

弗洛伊德精神分析人格理论 精神分析人格理论

奥地利精神病医生弗洛伊德是精神分析学派的创始人,弗洛伊德人格理论的内容主要包括人格结构、人格发展动力、人格适应及人格发展阶段。弗洛伊德人格性欲发展阶段因为这个理论中人格阶段的划分方式是根据性兴奋的不同部位所提出的。整

弗洛伊德.梅威瑟:家庭暴力阴影下成长起来的金钱梅

本帖最后由 看不下去 于 2013-11-17 14:50 编辑BY JOHNSON SNOWDEN弗洛伊德小梅威瑟发现自己正盯着一只猎枪枪管。 泪水以及随之而来的大哭预示着接下来他密西根州大急流城的家里将遭遇不幸。而那时候小梅还没满两岁。据滚石说,潜在

声明:《SPFA算法 弗洛伊德算法》为网友眼角耀眼的光分享!如侵犯到您的合法权益请联系我们删除