CODEWITHSUNDEEP
algorithmshortest-path
jack
jack

Reputation: 1951

Why Bellman-Ford algorithm needs v-1 passes?

I have not seen a graph that needs more than 2 passes using Bellman-Ford so far. Does any one have an example that really needs more than 2? (the algorithm says it needs v-1 passes in worst case). Thanks.

Upvotes: 1

Views: 1258

Answers (2)

jack
jack

Reputation: 1951

How many times actually depends on the order of visit, the best case is visiting the one that has the negative weight to broadcast in the first place, the worst case is visiting it in the last place (so you always needs many passes to propagate the negative weight to first-visited node).

Upvotes: 0

AbcAeffchen
AbcAeffchen

Reputation: 14977

A more interesting example: G=(V,E), V={1,...,n}, E={(j,1,2j), (i,i-1,1) for all j=3,...,n and i=2,...,n}. (Each edge is a tripe (a,b,w) meaning from a to b and w is the edge weight/distance.)

The graph looks like this: enter image description here

The distance to node 1 gets updated n-1 times.

Upvotes: 1

Related Questions