Detecting negative cycles using SPFA algorithm

4
votes

Using the SPFA algorithm below in a directed graph with negative and positive weights, how can we detect negative cycles?

procedure Shortest-Path-Faster-Algorithm(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
2
algorithmpathcycleshortest
From the proof of correctness: "The algorithm fails to terminate if negative-weight cycles are reachable from the source.", which is exactly what you would expect given the above pseudocode. There is no terminating condition other than the queue becomeing empty, which will not ever happen once a negative-weight cycle is encountered. If you want to introduce such a condition, you probably would end up doing something like the "does the n-th round produce a relaxation?" check of the Bellman-Ford algorithm. – G. Bach
So we have to check if any of the nodes is relaxed n times? – mehmetin
I haven't verified this idea carefully, but perhaps one could track the predecessor of each node and check every n/log n queue operations whether the graph of predecessors has a cycle. – David Eisenstat
@user2553636 That is one way you could do it. What David suggested is another (that could be done using a DFS, for example), although I don't know why he suggests to do it every n/log n queue operations. Could you maybe give some intuition for why you suggest the 1/log n factor, David? I'm afraid I can't see it. – G. Bach
Instead of relaxation, I checked if any of the nodes is queued n times. It works. – mehmetin

2 Answers

5
votes

The SPFA puts new nodes into the queue every time it sees a "better" edge to minimize your total distance, which is just Bellman-Ford's with better pruning. Bellman-Ford's Algorithm has proven that non-negative-weighted cycles have a maximum of |V| - 1 edges.

Thus, to check if a cycle is negatively-weighted, you just need to check if you used at least |V| edges during the run of your SPFA. In other words, check if you visited the same node at least |V| times.

Here's an appended pseudocode:

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

However, note that this won't get all nodes that are part of a negative-weight cycle. To get all nodes that are part of negative-weight cycles, do a DFS or BFS to mark all nodes reachable from u, where visits(u) = |V|.

Here's the final modified pseudocode:

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

The content of my answer will mostly be taken from this article.

In the original paper for the Bellman-Ford algorithm it was proven that in a directed weighted graph with no negative cycles, the shortest path has length at most |V|-1 edges.

We can use this fact to detect a negative cycle with the SPFA. We simply have to keep an additional array that stores the length (in number of edges) of the current shortest path for each vertex. Once this number reaches |V| for any vertex, we know that there is a negative cycle in the graph.

Below is the pseudocode for detecting negative cycles with SPFA. It has been modified so that each vertex has a starting "shortest path" of 0. This is equivalent to creating an imaginary source s and connecting s to every vertex with an edge of weight 0. This ensures that you can find negative cycles even if the graph isn't connected.

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"

If you want to find the negative cycle, you can read through the article linked above, as it tackles that as well.