What Is The Appropriate Action To Take When You're Shortest Path Algorithm Finds A Negative Weight Cycle?

Question

Typing out negative weight cycle again and again is kind of annoying, so for the rest of the question I'm going to abbreviate it to NWC.

I'm writing an optimized version of Bellman-Ford's Shortest Path Algorithm on a directed, weighted graph. When I give it a regular graph with no NWC's, it works fine, and finds the answer correctly. But when I give it a NWC, it loops forever. So, I put a system into the implementation where it finds out if there is a NWC, which it does correctly, but now I'm stuck on what to do once I find it.

My first thought was to just go on regularly while setting every vertex in the cycle to negative infinity, but every single vertex after that becomes negative infinity too, and soon enough, a huge chunk of the graph becomes negative infinity and I'm getting bugs left and right because I'm subtracting to negative infinity, adding to negative infinity, while also setting the distance to negative infinity. I technically could fix all the bugs, but then lot's of valuable information on the other vertices is lost because of one little NWC.

My next thought was to just terminate the program, but then again lot's of information is lost on the other vertices.

So, what is the correct action to be taken when you find a NWC?

Answer 1

You say that your implementation of Bellman-Ford loops forever. This leads me to believe that you are only stopping when no computed distance changes in one iteration.

You can always stop at the $(n-1)$-th iteration since, in the $i$-th iteration, all finite distances towards the vertices at hop-distance at most $i+1$ from the source must have correctly been computed.

Then, you can perform a single additional iteration. If a distance to a vertex $v$ changes during this iteration, then $v$ must be part of negative weight cycle (and you will find at least one such vertex $v$ per cycle). If $V$ is the set of these vertices $v$, you can mark all vertices reachable by those in $V$ has having "negative infinity" distance (you can do this in linear time w.r.t. the size of the graph by performing any graph visit).