Johnson Algorithm - Negative cycle check

Original Graph & Modified GraphI am using the BellmanFord algorithm to check the negative cycle for Johnson's algorithm.

The issue is after I add the extra node added with zero weights, the modified graph reports a negative cycle, while the original graph without the extra edge does not have any negative cycle.

My question is whether this can happen? If yes, how to detect negative cycle in Johnson's algorithm?

1 Answer
1

If your graph has no negative cycle or no cycle at all, adding a node and connecting it with a zero weight edge to the original graph will not add a cycle, especially not a negative cycle.

But I'm not sure if this is not a misunderstanding. If you just add a zero weight edge to a graph connecting two already existing nodes, this can add a negative cycle.
Just imaging a tree with only negative edge weights. It has no cycles. But if you add a zero weight edge, you close a cycle and since the edge weights are all negative the cycle will also have negative length.

I think in case of Johnson's algorithm you add out-edges from a new node to all existing nodes. So this cannot close any cycles because you can never come back to the new node.

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.