adelnobel's blog

Detecting negative cycles with SPFA (Shortest Path Faster Algorithm)
By adelnobel, 10 years ago, In English

Hi everyone,

I read about the SPFA a while ago and today I decided to try it out on some problems (for those who don't know about it

http://wcipeg.com/wiki/Shortest_Path_Faster_Algorithm

http://en.wikipedia.org/wiki/Shortest_Path_Faster_Algorithm )

Neither of the links above mentions anything about detecting negative cycles. Obviously, in the presence of a negative cycle, these implementations will never terminate. However, Steven Halim in his book says that it's sufficient to test whether a node entered the queue more than V - 1 times. Does anyone know a proof for this?

  • Vote: I like it
  • +9
  • Vote: I do not like it

»
10 years ago, # |
← Rev. 2   Vote: I like it +14 Vote: I do not like it

The correctness proof of Bellman–Ford works: If there is no negative cycle, a node will be relaxed at most n - 1 times (because that's the maximum length of a shortest path).

Now if you have finished SPFA with the addition of adding every node to the queue at most n - 1 times, you can just do a normal round of Bellman–Ford to determine whether there is a negative cycle: If any node gets relaxed during that round, there is one and the relaxed node is reachable from it via parent pointers in the shortest path tree.

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 5   Vote: I like it 0 Vote: I do not like it

    EDIT: Got it after some thinking about it, the correctness of the SPFA relies on using FIFO data structure to retain the same order of nodes sorted by edges length while relaxing like in bellman ford hence a node will be relaxed at most n-1 if there is no negative cycles times as in normal bellman-ford. Thanks alot for your help!

    I guess we can also do this in a different way, for each node on the queue we keep the length of the path to it in term of edges, and when the top node on the queue has length N then there must've been a negative cycle, I think this is also correct (someone corrects me if it's not)

    → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It will be much faster if using a stack.

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +9 Vote: I do not like it

Coincidentally, I just wrote a blog entry about this.

Instead of stopping when a vertex is pushed into the queue $$$n$$$ times, i keep track of the current path length for each vertex and stop once one has length $$$n$$$.

However, in the presence of a negative cycle, this is still slow and we can do better.

Further down in the post I tested a variant using link/cut trees to immediately detect once a cycle forms, enabling us to terminate early. This has proven to give a huge performance boost when there is a negative cycle, but is a bit slower than the original spfa when there are no negative cycles.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Update:

    I found out that using a link/cut tree isn't the most optimal way to do this. Doing a simple DFS to check for cycles every $$$n$$$ iterations turns out to be a bit faster and much easier to implement.

    Again, visit my blog if you are interested :)

    → Reply