首页 > 代码库 > shortpath_SPAF

shortpath_SPAF

SPFA算法

SPFA()其实是Bellman的一个小变形 

该算法常用来计算差分约束系统,因为常常有负值边存在。

为了简便,我们约定图中不存在负权回路,这可以通过一次拓扑排序知道。SPFA实际是Bellman-Ford算法的一种队列实现,用一个数组来保存最短路径的估计值,初始时将源加入队列,每次从队列中取队头元素,并对所有与其相邻的结点进行松弛操作,如果该点的估计值有所调整,且该点不在队列中,则入队,如此反复,直到队空

定理1SPFA算法采用的动态优化方法,能够使得路径估计值变得越来越小,优化过程是正确的。

证明:算法中每一步都是从该队取出点来优化其它各点。现假设算法结束时计算的结果不是最短路径,即从原点到某些点还存在着更短的路径,而算法规定:只要存在着比D[j]更短的路径,即D[j]>D[w]+l(w,j),那么D[j]就一定要被优化且j点就要入队,算法就不会结束。所以上述假定不成立,算法的执行会使路径估计值变得越来越小,逼近直至达到最短路径,优化过程正确。

定理2SPFA算法的优化过程是收敛的,不会形成无限循环,算法能够正常结束。

证明:在任意一个具有循环结构的算法或程序中,所谓不收敛就是死循环。SPFA算法中,循环控制是由队列是否为空为条件的,若队列不为空,继续循环;若队列为空,循环终止,算法结束。在SPFA算法的循环中,既有从队列取出来进行优化的队减操作,也有被优化后的点入队的队增操作,则要注意,某任意顶点j入队是有先决条件的,亦即D[j]>D[w]+l(w,j)j点入队的同时,D[j]也就被优化取值为较小的D[w]+l(w,j)这样使得各点的路径值D[j]变得越来越小,直到最终优化为最短路径,此时就不会再有任何点被继续优化的可能,因而就不会再有顶点入队,仅有队减操作直到队空循环终止。

算法描述

输入设L是用来表示有向图G=(V,E)的邻接表,邻接表元素l是有向图各边的权值,输入各边的权值l(v,k)建立邻接表L.

输出设D数组是记录当前从源点到其余各点的最短路径的值,初始化时D数组的每个元素都为最大值,经过SPFA算法D数组输出各点的最短路径值。

算法的形式算法描述及注释:

1    begin      //算法开始

2    for each v in V do

             Begin

                    For each kL[v] do read (l(v,k)); //读入每条边的权值到邻接表

                    QM[v]=0;      //初始化每个顶点是否在队里的标志数组

                    D[v]=MAX//将最短路径数组初始化为最大值

             End;

3          queue<-v0;

QM[v0]=1;                  //源点v0queue

4    D[v0]=0                  //源点到源点本身的路径值赋值为零

5    while queue not empty do

             Begin

                    W<-queue;    //queue中取出一个点w

                    QM[w]=0;     //w点出队后,其标志数组元素改为零,表示w点不在队列

6                                      for each jL[w] do

7                if D[j]>D[w]+l(w,j) then

                           begin

8                                D[j]=D[w]+l(w,j)  //判断经过w点到j点的路径是比原来的路径D[j]更短后,对j点的路径进行优化

                                  If QM[j]==0 then

                                  Begin

                                         Queue<-j;

                                         QM[j]=1;       //j点不在队列里,j入队,并且将QM[j]标志置为1表示j已入队

                                  End

                           End

            End;

9          for each v in V do

begin

             write(D[v]);

end; //优化完成后,D数组存放的就是从源点到各点的最短路径值,可以输出结果

10   end.

定理对于任意的有向图G=(V,E),设边的总数为e,顶点的总数为nSPFA算法的时间复杂性为O(e).(!!!)

证明:SPFA算法首先进行初始化,初始化主要是读入有向图的每一条边的权值,显然需用的时间为O(e),初始化后,SPFA算法首先将源点入队,然后从队列里取出队首的一个顶点作为w点,这里没有像Dijkstra算法那样从V-S集合中选一个具有最小D[w]w点,所以省去了选择所花费的时间,SPFA算法的时间复杂性主要是由while循环所决定的。由于采用邻接表作为图的数据结构,第(6)句就是对一个点的表所连接的所有边进行优化,而每一个点的表长是与该点的出度有关。因为n个点的出度总和就是有向边的边数e,那么对于一个点来说,其平均出度就是e/n所以第(6)句的执行时间平均为O(e/n)                                                 

       设第(5)while循环的次数为m,即为顶点入队的次数,若平均每一个点入队一次,则m=n;若平均每个点入队两次,则m=2n,算法编程后实际运行试算情况表明,m一般没有超过2n。事实上,虽然顶点入队次数m是一个事先不易分析出的数,但它确是一个随图的不同而略有不同的常数,一旦图确定,各边的权值确定,源点确定,m也就是一个确定的常数,所以SPFA算法的时间复杂性为

               T=O(m*e/n)=O(m/n*e)              K=m/n                     T=O(k*e)

因为K是一个常数,所以SPFA算法的时间复杂性为O(e)。(证毕)