Shortest paths with negative weights You run |V| − 1 passes of Bellman-Ford, then one more pass, and during that extra pass some distance value decreases. What does that tell you?

Question

Accepted Answer

The graph has a negative cycle reachable from the source.

Answer

The edge order was unlucky and the algorithm should be restarted.

Answer

The graph has a cycle, which may or may not be negative.

Answer

That vertex is unreachable from the source.

Answer

Nothing in particular; a decrease on the extra pass is normal.

Crowdly

Shortest paths with negative weights You run |V| − 1 passes of Bellman-Ford, the...

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