CODEWITHSUNDEEP
graph-algorithm
shibu thomas
shibu thomas

Reputation: 11

Johnson Algorithm - Negative cycle check

I 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?

Original Graph & Modified Graph

Upvotes: 0

Views: 626

Answers (1)

AbcAeffchen
AbcAeffchen

Reputation: 15017

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.

Upvotes: 2

Related Questions