SPFA-最短路径快速算法-hihocode185

算法 hihocode

稀疏图$\{V, E\}(|V| << |E|)$中，计算从源点$s$出发，到达终点$e$的最短路径，利用SPFA进行快速计算。
SPFA算法类似于BFS，是bellman-ford算法的一种队列实现，减少了不必要的冗余计算。

算法如下：

• 数据结构

neib[N][N] //记录邻接数据
vis[N];    //记录节点i是否在队列中,-1表示不在队列中，1表示在
dis[N];    //从源点s出发到当前结点的最短距离,初始为INF
queue q;   //待处理的结点队列
// count[N]; //计数，可以用来检测负权边

• 算法流程

void spfa()
{
    q.push(s);
    vis[s] = 1;
    dis[s] = 0;
    while(q.empty())
    {
       cur = q.front(); q.pop();
       vis[cur] = -1;
       for(cur的每一个邻接点e)
       {
            if(e 不合法）continue; //越界之类
            if(dis[e] > dir[cur] + neid[s][e]) //松弛
            {
                dis[e] = dir[cur] + neid[s][e];
                if(vis[e] == -1）//e不在队列中
                {
                    q.push(e);
                    vis[e] = 1;
                }
            }
       }
    }
}

与BFS不同的是，入队操作需要在松弛完成之后，而且BFS中一旦一个结点入队之后，就不可能再次入队，但是SPAF中是可以的，因为结点到源点的距离松弛之后，可能会影响到后续节点，所以后续结点就得再次入队进行处理。

需要注意的是，SPFA算法的复杂度为$O(kE)$，其中$k$为节点平均入队次数，据证明一般为2（其实并不严谨）。因此，SPFA算法或者说bellman-ford算法对复杂度并没有保证（构造一些特殊数据就会把$k$提的很高）。但是优点在于实现简单，如果记录每个结点的入队次数，也能够检测图中的负权边。

转一个知乎上的解答

SPFA在稀疏图上快，因为是通过边来增广的。dijkstra在稠密图上快。因为是通过点来增广的。某些情况下dijkstra 加上堆优化，在处理大数据的时候会比SPFA快很多；但是SPFA在随机数据的综合表现中相比dijkstra优势还是比较大的。总而言之，各有所长。

-----作者：匿名用户
链接：https://www.zhihu.com/question/27312074/answer/36223913
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。