Shortest paths with negative weights Assume a graph where no negative cycle is reachable from the source. Bellman-Ford repeats its pass over all the edges |V| − 1 times. Why are that many passes sufficient?

Question

Accepted Answer

A shortest path then uses at most |V| − 1 edges, and after k passes every distance whose shortest path uses at most k edges is correct.

Answer

After |V| − 1 passes every edge has been relaxed |V| − 1 times, which is enough for any graph at all.

Answer

It is a safety margin; half as many passes would always do.

Answer

|V| − 1 is the largest number of negative edges a graph can have without a negative cycle.

Answer

Each pass changes at least one distance, so |V| − 1 passes change |V| − 1 of them.

Crowdly

Shortest paths with negative weights Assume a graph where no negative cycle is r...

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