[关闭]
@markheng 2018-01-16T02:51:49.000000Z 字数 1010 阅读 1545

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

算法 hihocode


稀疏图中,计算从源点出发,到达终点的最短路径,利用SPFA进行快速计算。
SPFA算法类似于BFS,是bellman-ford算法的一种队列实现,减少了不必要的冗余计算。

算法如下:

  1. neib[N][N] //记录邻接数据
  2. vis[N]; //记录节点i是否在队列中,-1表示不在队列中,1表示在
  3. dis[N]; //从源点s出发到当前结点的最短距离,初始为INF
  4. queue q; //待处理的结点队列
  5. // count[N]; //计数,可以用来检测负权边
  1. void spfa()
  2. {
  3. q.push(s);
  4. vis[s] = 1;
  5. dis[s] = 0;
  6. while(q.empty())
  7. {
  8. cur = q.front(); q.pop();
  9. vis[cur] = -1;
  10. for(cur的每一个邻接点e)
  11. {
  12. if(e 不合法)continue; //越界之类
  13. if(dis[e] > dir[cur] + neid[s][e]) //松弛
  14. {
  15. dis[e] = dir[cur] + neid[s][e];
  16. if(vis[e] == -1//e不在队列中
  17. {
  18. q.push(e);
  19. vis[e] = 1;
  20. }
  21. }
  22. }
  23. }
  24. }

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

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

转一个知乎上的解答

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

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

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注