Reputation: 19
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