algorithm - 使用 SPFA 算法检测负循环

Question

在具有负权重和正权重的有向图中使用下面的 SPFA 算法，我们如何检测负循环？

程序最短路径更快算法(G, s)

  1    for each vertex v ≠ s in V(G)
  2        d(v) := ∞
  3    d(s) := 0
  4    push s into Q
  5    while Q is not empty
  6        u := pop Q
  7        for each edge (u, v) in E(G)
  8            if d(u) + w(u, v) < d(v) then
  9                d(v) := d(u) + w(u, v)
 10                if v is not in Q then
 11                    push v into Q

Answer 1

SPFA 每次看到“更好”的边缘时都会将新节点放入队列中以最小化您的总距离，这只是 Bellman-Ford 具有更好的修剪。 Bellman-Ford 算法已证明非负加权循环最多有 |V| - 1 个边。

因此，要检查循环是否为负权重，您只需检查在 SPFA 运行期间是否至少使用了 |V| 条边。换句话说，检查您是否访问过同一节点至少 |V| 次。

这是一个附加的伪代码:

procedure SPFA(G, s)
    for each vertex v ≠ s in V(G)
        d(v) := ∞
        visits(v) := 0
    d(s) := 0
    push s into Q
    while Q is not empty
        u := pop Q
        visits(u) := visits(u) + 1                      // increment visit count
        if visits(u) < |V| then                         // relaxation step
            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
                        push v into Q

但是，请注意，这不会获得属于负权重循环的所有节点。要获得属于负权重循环的所有节点，请执行 DFS 或 BFS 以标记可从 u 访问的所有节点，其中 visits(u) = | V|.

这是最终修改后的伪代码:

procedure DFS(G, u, visited)
    if visited(u) = false then
        visited(u) := true
        for each edge (u, v) in E(G)
            DFS(G, v, visited)

procedure SPFA(G, s)
    for each vertex v ≠ s in V(G)
        d(v) := ∞
        visits(v) := 0
    d(s) := 0
    push s into Q
    while Q is not empty
        u := pop Q
        visits(u) := visits(u) + 1                      // increment visit count
        if visits(u) < |V| then                         // relaxation step
            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
                        push v into Q
    for each vertex u in V(G)
        visited(u) := false
    for each vertex u in V(G), where visits(u) = |V|
        DFS(G, u, visited)
    for each vertex u in V(G), where visited(u) = true
        d(u) := -∞