Dijkstra VS SPFA

Dijkstra算法思路的核心就是每次找一个未被标记的距离最短的点来松弛和它相连的边,用STL的优先队列实现堆优化后,时间复杂度是O((V+E)lgv)

SPFA是BellmanFord的一种优化,根据论文的证明时间复杂度[大概]是O(kE)。其思路是:每次对队首的点进行松弛相连的边,只要松弛成功,判断该相连的点是否在队列中,如果不在就入队。因此我们看到一个很明显的区别就在于SPFA的队列一个点可以进队多次。

  • Dijkstra是每次确定了到一个点的最短距离,再用该点更新到其它点的距离。不能处理有负边的图。因为Dijkstra每次选的是当前能连到的边中权值最小的,在正权图中这种贪心是对的,但是在负权图中就不是这样了。如下图,1——>2权值为2,1——>3权值为3,3——>2权值为-2,求1到2的最短路径时,Dijkstra就会选择权为2的1——>2,但实际上1——>3——>2才是最优的结果。其路径长为1.
    《Dijkstra VS SPFA》

  • SPFA是用双端队列,每次取出队头,来更新距离,它之后可能还会入队。它是一种动态逼近法,因为每次松弛距离都会减小,所以松弛一定会有结束的。如果一个点入队超过n次就是存在负环。

  • SPFA可以判断负环:判断一个点是否进队的次数>n(n为所有节点的个数)。如果包含负环,则意味着最短路径不存在。因为只要在负权回路上不断兜圈子,所得的最短路长度可以任意小。

  • SPFA可以被卡专门造的数据,例如这篇博客的SPFA-killer

总结:
Dijkstra的稳定性好,在稠密图更快,但不能解决有负权边的问题。SPFA可以解决负权边、判断负环是否存在,在稀疏图更快,但是稳定性差、比赛如果不是随机数据可能被卡掉。

另附Dijlstra模板与SPFA模板,调用的时候例如for (int i=1;i<=n;i++) dis[i] = 1e18; dij(1, dis);:就可以计算从顶点1到所有点的距离保存在dis数组中。

点赞
  1. anita说道:

    感觉prim更好记,那个SPFA的条件是先更新后更新在不在队列的标志我总是忘掉,而且SPFA不需要优秀队列,总忘掉。。。

  2. anita说道:

    Prim模板
    ans = 0;
    int mind = 1e9, mini;
    dist[1] = 0;
    rep (i,1,n){
    mind = 1e9;
    rep (j,1,n)
    if (!vis[j]&&dist[j]<mind){
    mind = dist[j];
    mini = j;
    }
    int u = mini;
    ans += mind;
    vis[u] = true;
    rep (j,1,n){
    if (g[u][j]<dist[j]){
    dist[j] = g[u][j];
    }
    }
    }

发表评论

电子邮件地址不会被公开。 必填项已用*标注