SPFA算法求最短路，比Dijstra和Bellman-ford还好

http://blog.csdn.net/v_JULY_v/article/details/6277490

那么，究竟什么是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 ← Ø 　　
3. for each vertex ∈ V[G] 　　
4. q[v]=0 　　
5. ENQUEUE(Q,s) 　　
6. q[s]=1 　　
7. while Q≠Ø 　　
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<与 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    输出：一行有两个数， 最短距离及其花费。

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

int d[1005][2];
bool used[1005];
vectormap[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//遍历
        {
            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

完。