SPFA算法简介

Author: 2015-08-23

ACM

, ,

　　SPFA（Shortest Path Faster Algorithm）算法是Bellman-Ford的一个增强版，SPFA算法在随机稀疏图上表现良好，尤其适用于带负权边的情况，但在最差情况下效率和Bellman-Ford一样糟糕。如果没有负权边，选择Dijkstra算法更佳。

　　SPFA算法的基本思想和Bellman-Ford一样，对于有V个顶点和E条边的图，Bellman-Ford需要V-1次循环，每次循环里都要遍历E条边，但只有在发生松弛时才会更新距离，浪费了大量操作。SPFA算法维护了一个存储顶点的队列，只有当某条边发生松弛时，才将该边的终点加入队列，直到队列为空，即无法再松弛时结束。

　　Wiki上给出SPFA算法的伪代码如下：

procedure Shortest-Path-Faster-Algorithm(G, s)
    for each vertex v ≠ s in V(G)
        d(v) := ∞
    d(s) := 0
    offer s into Q
    while Q is not empty
        u := poll Q
        for each edge (u, v) in E(G)
            if d(u) + w(u, v) < d(v) then
                d(v) := d(u) + w(u, v)
                if v is not in Q then
                    offer v into Q

　　算法的输入为图G和起点s，算法流程如下：

  1. 初始化起点到其他点的距离d(v) （v != s）为无穷，初始化起点到起点的距离d(s) 为0。
  2. 将起点s入队。
  3. 队不为空时，重复操作：
    1. 从队中取出一个顶点u；
    2. 遍历所有以u为起点的边，以u为起点的边(u, v)的权值为w(u, v) ，如果的边(u, v)能够使起点到v的距离缩短，即从起点先到u再由边(u, v)到v的距离，短于起点直接到v的距离（d(u) + w(u, v) < d(v) ），则发现了一条更短的从起点到达v的路径，更新起点到v的距离d(v) 为d(u) + w(u, v) ，并将点v入队。

　　上面的算法可以求得单源最短路径，但无法判断负权环的情况。如果存在负权环，负权环上的点可以进行无限的松弛，不停地入队，导致死循环。要判断负权环，只需加入一个额外的数组cnt ，cnt(u) 记录了点u入队的次数，如果u入队的次数超过顶点总数，则说明有负权环。因为对于一个有V个顶点的图，其中两点之间的最短路径最多包含V-1条边，松弛次数超过顶点数，表明最短路径上包含了重复的边，这正是由负权环导致的。修改后的伪代码如下所示：

procedure Shortest-Path-Faster-Algorithm(G, s)
    for each vertex v ≠ s in V(G)
        d(v) := ∞
        cnt(v) := 0
    d(s) := 0
    offer s into Q
    while Q is not empty
        u := poll Q
        cnt(u) :=  cnt(u) + 1
        if cnt(u) > V 
            error "Graph contains a negative-weight cycle"
        for each edge (u, v) in E(G)
            if d(u) + w(u, v) < d(v) then
                d(v) := d(u) + w(u, v)
                if v is not in Q then
                    offer v into Q