十三、通过浙大上机复试试题学SPFA 算法

十三、通过浙大上机复试试题学SPFA 算法

作者：July、sunbaigui。二零一一年三月二十五日。
出处：http://blog.csdn.net/v_JULY_v。
------------------

前言：
本人不喜欢写诸如“如何学算法”此类的文章，一来怕被人认为是自以为是，二来话题太泛，怕扯得太远，反而不着边际。所以，一直不打算写怎么学习算法此类的文章。

不过，鉴于读者的热心支持与关注，给出以下几点小小的建议，仅供参考：
1、算法，浩如烟海，找到自己感兴趣的那个分支，或那个点来学习，然后，一往无前的深入探究下去。
2、兴趣第一，一切，由着你的兴趣走，忌浮躁。
3、思维敏捷。给你一道常见的题目，你的头脑中应该立刻能冒出解决这道问题的最适用的数据结构，以及算法。
4、随兴趣，多刷题。ACM题。poj，面试题，包括下文将出现的研究生复试上机考试题，都可以作为你的编程练习题库。
5、多实践，多思考。学任何一个算法，反复研究，反复思考，反复实现。
6、数据结构是一切的基石。不必太过专注于算法，一切算法的实现，原理都是依托数据结构来实现的。弄懂了一个数据结构，你也就通了一大片算法。
7、学算法，重优化。
8、学习算法的高明之处不在于某个算法运用得有多自如，而在于通晓一个算法的内部原理，运作机制，及其来龙去脉。

ok，话不再多。希望，对你有用。
接下来，咱们来通过最近几年的浙大研究生复试上机试题，来学习或巩固常用的算法。

浙大研究生复试2010年上机试题-最短路径问题
问题描述：
给你n个点，m条无向边，每条边都有长度d和花费p，给你起点s终点t，要求输出起点到终点的最短距离及其花费，如果最短距离有多条路线，则输出花费最少的。

输入：输入n,m，点的编号是1~n,然后是m行，每行4个数 a,b,d,p，表示a和b之间有一条边，且其长度为d，花费为p。最后一行是两个数 s,t;起点s，终点t。n和m为0时输入结束。
(1<n<=1000, 0<m<100000, s != t)
输出：一行有两个数， 最短距离及其花费。（下文，会详细解决）

几个最短路径算法的比较
ok，怎么解决上述的最短路径问题列?提到最短路径问题，想必大家会立马想到Dijkstra 算法，但Dijkstra 算法的效率如何列?
我们知道，Dijkstra 算法的运行时间，依赖于其最小优先队列的采取何种具体实现决定，而最小优先队列可有以下三种实现方法：
1、利用从1至|V| 编好号的顶点，简单地将每一个d[v]存入一个数组中对应的第v项，
如上述DIJKSTRA（G，w，s）所示，Dijkstra 算法的运行时间为O(V^2+E)。
2、如果是二叉/项堆实现最小优先队列的话，EXTRACT-MIN(Q)的运行时间为O(V*lgV)，
所以，Dijkstra 算法的运行时间为O(V*lgV+E*lgV)，
若所有顶点都是从源点可达的话，O（(V+E)*lgV）=O（E*lgV）。
当是稀疏图时，则E=O(V^2/lgV)，此Dijkstra 算法的运行时间为O(V^2)。
3、采用斐波那契堆实现最小优先队列的话，EXTRACT-MIN(Q)的运行时间为O(V*lgV)，
所以，此Dijkstra 算法的运行时间即为O(V*lgV+E)。

综上所述，此最小优先队列的三种实现方法比较如下：

EXTRACT-MIN + RELAX
I、 简单方式： O（V*V + E*1）
II、 二叉/项堆： O（V*lgV + |E|*lgV）
源点可达：O（E*lgV）
稀疏图时，有E=o（V^2/lgV），
=> O（V^2）
III、斐波那契堆：O（V*lgV + E）

是的，由上，我们已经看出来了，Dijkstra 算法最快的实现是，采用斐波那契堆作最小优先队列，算法时间复杂度，可达到O（V*lgV + E）。

但是列?如果题目有时间上的限制列?vlgv+e的时间复杂度，能否一定满足要求?我们试图寻找一种解决此最短路径问题更快的算法。

这个时候，我们想到了Bellman-Ford算法：求单源最短路，可以判断有无负权回路（若有，则不存在最短路），时效性较好，时间复杂度O（VE）。不仅时效性好于上述的Dijkstra 算法，还能判断回路中是否有无负权回路。

既然，想到了Bellman-Ford算法，那么时间上，是否还能做进一步的突破。对了，我们中国人自己的算法--SPFA算法：SPFA算法，Bellman-Ford的队列优化，时效性相对好，时间复杂度O（kE）。（k<<V）。
是的，线性的时间复杂度，我想，再苛刻的题目，或多或少，也能满足要求了。

什么是SPFA算法
在上一篇文章二之三续、Dijkstra 算法+Heap堆的完整c实现源码中，我们给出了Dijkstra+Heap堆的实现。其实，在稀疏图中对单源问题来说SPFA的效率略高于 Heap+Dijkstra ；对于无向图上的APSP(All Pairs Shortest Paths)问题，SPFA算法加上优化后效率更是远高于Heap+Dijkstra。

那么，究竟什么是SPFA算法列?

SPFA算法，Shortest Path Faster Algorithm，是由西南交通大学段凡丁于1994年发表的。正如上述所说，Dijkstra 算法无法用于负权回路，很多时候，如果给定的图存在负权边，这时类似Dijkstra等算法便没有了用武之地，而Bellman-Ford算法的复杂度又过高，SPFA算法便派上用场了。
　　
简洁起见，我们约定有向加权图G不存在负权回路，即最短路径一定存在。当然，我们可以在执行该算法前做一次拓扑排序，以判断是否存在负权回路。

我们用数组d记录每个结点的最短路径估计值，而且用邻接表来存储图G。
我们采取的方法是动态逼近法：设立一个先进先出的队列用来保存待优化的结点，优化时每次取出队首结点u，并且用u点当前的最短路径估计值对离开u点所指向的结点v进行松弛操作，如果v点的最短路径估计值有所调整，且v点不在当前的队列中，就将v点放入队尾。
这样不断从队列中取出结点来进行松弛操作，直至队列空为止。

定理: 只要最短路径存在，上述SPFA算法必定能求出最小值。
期望的时间复杂度O(ke)， 其中k为所有顶点进队的平均次数，可以证明k一般小于等于2。

SPFA实际上是Bellman-Ford基础上的优化，以下，是此算法的伪代码：

//这里的q数组表示的是节点是否在队列中，如q[v]=1则点v在队列中　
SPFA(G,w,s)　 　　
1. INITIALIZE-SINGLE-SOURCE(G,s) 　　
2. Q ← &Oslash; 　　
3. for each vertex ∈ V[G] 　　
4. q[v]=0 　　
5. ENQUEUE(Q,s) 　　
6. q[s]=1 　　
7. while Q≠&Oslash; 　　
8. do u ← DEQUEUE(Q) 　　
9. q[u]=0 　　
10.for each edge(u,v) ∈ E[G] 　　
11. do t ← d[v] 　　
12. RELAX(u,v,w) 　　
13. π[v] ← u 　　
14. if (d[v] < t) 　　
15. ENQUEUE(Q,v) 　　
16. q[v]=1

SPFA是Bellman-Ford的队列优化，时效性相对好，时间复杂度O（kE）。（k<<V）。
与Bellman-ford算法类似，SPFA算法采用一系列的松弛操作以得到从某一个节点出发到达图中其它所有节点的最短路径。所不同的是，SPFA算法通过维护一个队列，使得一个节点的当前最短路径被更新之后没有必要立刻去更新其他的节点，从而大大减少了重复的操作次数。

与Dijkstra算法与Bellman-ford算法不同，SPFA的算法时间效率是不稳定的，即它对于不同的图所需要的时间有很大的差别。在最好情形下，每一个节点都只入队一次，则算法实际上变为广度优先遍历，其时间复杂度仅为O(E)。另一方面，存在这样的例子，使得每一个节点都被入队(V-1)次，此时算法退化为Bellman-ford算法，其时间复杂度为O(VE)。有研究指出在随机情形下平均一个节点入队的次数不超过2次，因此算法平均的时间复杂度为O(E)，甚至优于使用堆优化过的Dijkstra算法。

最短路径问题的解决
浙大研究生复试2010年上机试题-最短路径问题
问题描述：
给你n个点，m条无向边，每条边都有长度d和花费p，给你起点s终点t，要求输出起点到终点的最短距离及其花费，如果最短距离有多条路线，则输出花费最少的。

输入：输入n,m，点的编号是1~n,然后是m行，每行4个数 a,b,d,p，表示a和b之间有一条边，且其长度为d，花费为p。最后一行是两个数 s,t;起点s，终点t。n和m为0时输入结束。
(1<n<=1000, 0<m<100000, s != t)
输出：一行有两个数， 最短距离及其花费。

接下来，咱们便利用SPFA 算法来解决此最短路径问题。
以下，便引用sunbaigui的代码来说明此问题：
声明几个变量：

int d[1005][2];
bool used[1005];
vector<Node>map[1005];
int N,M,S,T;

建个数据结构：

struct Node
{
    int x,y,z;
    Node(int a=0,int b=0,int c=0):x(a),y(b),z(c){}
};

以下是关键代码

//sunbaigui：
//首先将起点弹入队列，用used数组标记i节点是否在队列中，
//然后从队列中弹出节点，判断从这个弹出节点能到达的每个节点的距离是否小于已得到的距离，
//如果是则更新距离，然后将其弹入队列，修改used数组。
void spfa()
{
    queue<int>q;   //构造一个队列
    q.push(S);    
    memset(used,false,sizeof(used));
    int i;
    for(i=1;i<=N;i++)
        d[i][0]=d[i][1]=-1;     
    d[S][0]=d[S][1]=0;         //初始化
    while(!q.empty())
    {
        int node=q.front();
        q.pop();
        used[node]=false;
        int t,dis,p;
        for(i=0;i<map[node].size();i++)   //遍历
        {
            t=map[node][i].x;
            dis=map[node][i].y;
            p=map[node][i].z;
            if(d[t][0]==-1||d[t][0]>d[node][0]+dis)  
            {
                d[t][0]=d[node][0]+dis;  //松弛操作
                d[t][1]=d[node][1]+p;     
                if(!used[t])
                {
                  used[t]=true; 
                  q.push(t);     //t点不在当前队列中，放入队尾。
                }
            }
            else if(d[t][0]!=-1&&d[t][0]==d[node][0]+dis)
            {
                if(d[t][1]>d[node][1]+p)
                {
                    d[t][1]=d[node][1]+p;
                    if(!used[t])
                    {
                      q.push(t);
                      used[t]=true;
                    }
                }
            }
        }
        
    }   
}

主函数测试用例：

int main()
{
    while(scanf("%d %d",&N,&M)!=EOF)
    {
        if(N==0&&M==0)break;
        int s,t,dis,p;
        int i;
        for(i=1;i<=N;i++)
            map[i].clear();
        while(M--)
        {
            scanf("%d %d %d %d",&s,&t,&dis,&p);
            map[s].push_back(Node(t,dis,p));
            map[t].push_back(Node(s,dis,p));
        }
        scanf("%d %d",&S,&T);
        spfa();
        printf("%d %d\n",d[T][0],d[T][1]);
    }
    return 0;
}

运行结果，是：

最后，总结一下（Lunatic Princess）：
(1)对于稀疏图，当然是SPFA的天下，不论是单源问题还是APSP问题，SPFA的效率都是最高的，写起来也比Dijkstra简单。对于无向图的APSP问题还可以加入优化使效率提高2倍以上。
(2)对于稠密图，就得分情况讨论了。单源问题明显还是Dijkstra的势力范围，效率比SPFA要高2-3倍。APSP问题，如果对时间要求不是那么严苛的话简简单单的Floyd即可满足要求，又快又不容易写错；否则就得使用Dijkstra或其他更高级的算法了。如果是无向图，则可以把Dijkstra扔掉了，加上优化的SPFA绝对是必然的选择。

稠密图 稀疏图有负权边
----------------------------------------------------------------------------------------------
单源问题 Dijkstra+heap SPFA(或Dijkstra+heap,根据稀疏程度) SPFA
APSP(无向图) SPFA(优化)/Floyd SPFA(优化) SPFA(优化)
APSP(有向图) Floyd SPFA (或Dijkstra+heap,根据稀疏程度)SPFA

完。

版权所有。转载本BLOG内任何文章，请以超链接形式注明出处。
否则，一经发现，必定永久谴责+追究法律责任。谢谢，各位。