You are given a weakly connected directed weighted graph — connected when the edge directions are ignored — and asked whether it contains a negative cycle anywhere — not just one reachable from some particular vertex. Which approach settles it in O(|V| · |E|) time?

Question

You are given a  weakly connected  directed weighted graph — connected when the edge directions are ignored — and asked whether it contains a negative cycle  anywhere — not just one reachable from some particular vertex. Which approach settles it in O(|V| · |E|) time?

Accepted Answer

Add one new vertex with a zero-weight edge to every other vertex, and run Bellman-Ford once from the new vertex

Answer

Reverse every edge and run Bellman-Ford once from any vertex

Answer

Run Bellman-Ford from every vertex in turn and check each extra round

Answer

Run Bellman-Ford once from any vertex and check the extra round

Crowdly

You are given a weakly connected directed weighted graph — connected when the ...

Want instant access to all verified answers on learning.monash.edu?