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?

  • $\begingroup$ Is it a directed or an undirected graph? $\endgroup$ – Steven Apr 6 '20 at 22:02
  • $\begingroup$ Directed, weighted. $\endgroup$ – nishantc1527 Apr 6 '20 at 22:05
  • $\begingroup$ When you say " lot's of valuable information on the other vertices is lost because of one little NWC", there is no information to be lost... it doesn't make sense to assign any finite distance to the vertices reachable by a NWC. The distances you have computed so far are incorrect. You can only report finite distances for the vertices unreachable by NWCs and set the other distances to $-\infty$. $\endgroup$ – Steven Apr 6 '20 at 22:24

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).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.