Eric
Eric

Reputation: 19

What is an example of the worst-case scenario for the Bellman-Ford algorithm?

I am wondering what would the worst case look like for Bellman-Ford algorithm to have to traverse all edges V-1 time, cause most of the time it won't need V-1 iterations to find all shortest path. According to geeksforgeeks, it states that

The worst-case time complexity of Bellman-Ford algorithm is also O(V*E). This scenario occurs when the algorithm needs to iterate through all vertices and edges for |V| - 1 passes, followed by one more pass for detecting negative weight cycles.

But I don't really get what does it mean and cannot come up with a concrete example, can anyone shed some light on this with an example?

Upvotes: 0

Views: 13

Answers (0)

Related Questions