使用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

- mehmetin

---

根据正确性证明：“如果源点到达负权环，则算法无法终止。” 这正是您根据上述伪代码所期望的。除了队列变为空之外，没有任何终止条件，一旦遇到负权环就永远不会发生。如果您想引入这样的条件，您可能会做类似于Bellman-Ford算法的“第n轮是否产生松弛？”检查。 - G. Bach

那么我们需要检查任何一个节点是否被松弛n次？ - mehmetin

我还没有仔细验证这个想法，但也许可以跟踪每个节点的前任，并检查每个n / log n队列操作是否前任图中有循环。 - David Eisenstat

@user2553636 那是一种你可以做的方式。David 建议的是另一种方法（例如可以使用 DFS），尽管我不知道他为什么建议每 n/log n 次队列操作就执行一次。David 你能解释一下为什么建议使用 1/log n 的因子吗？恐怕我看不懂。 - G. Bach

不是放松，而是我检查了节点是否排队了n次。它有效。 - mehmetin

@cassius_41272 虽然你所写的是正确的，但在这样做时必须非常小心 - 你需要确保你的 Q 是先进先出的，并且除非每次将 n 推入队列时，否则不要将其计为已排队，而是每次从队列中弹出 n 并且 d(n) 与将其推入队列时相同。 - siemanko

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) := -∞

- Enrico Tiongson

Answer 2

我的答案的内容主要来自于this article。

在Bellman-Ford算法的原始论文中，证明了在一个有向加权图中，如果没有负环，则最短路径的长度最多为|V|-1条边。

我们可以利用这个事实来使用SPFA检测负环。我们只需要保持一个额外的数组，存储每个顶点当前最短路径的长度（以边数计算）。一旦任何顶点的这个数字达到|V|，我们就知道图中存在负环。

下面是使用SPFA检测负环的伪代码。它已经被修改，使得每个顶点都有一个起始的“最短路径”为0。这相当于创建一个虚拟源s，并将s连接到每个顶点，边的权重为0。这确保即使图不连通，也能找到负环。

function SPFA(G):
    for v in V(G):
        len[v] = 0
        dis[v] = 0
        Queue.push(v)
    while !Queue.is_empty():
        u = Queue.pop()
        for (u, v) in E(G):
            if dis[u] + w(u, v) < dis[v]:
                len[v] = len[u] + 1
                if len[v] == n:
                    return "negative cycle detected"
                dis[v] = dis[i] + w(u, v)
                if !Queue.contains(v):
                    Queue.push(v)
    return "no negative cycle detected"

如果你想要“找到”负环，你可以阅读上面链接的文章，它也会处理这个问题。

- KonaeAkira