How to make bellman-ford run in worst case?

Question

I am trying to make optimized version of bellman ford algorithm to run in worst case. Optimized version I mean if after relaxing 1 round of edges and there is no further update on the shortest distance, it terminates.

For instance, a simple connected weighted directed graph with 7 vertices such that running Optimized Bellman-Ford's algorithm from source vertex 0 uses at least 5 rounds to get the correct shortest paths.

The graph cannot contain a negative weight cycle. i.e. all outgoing edges from vertex 0 is processed then edges from vertex 1 and so on

I know it has to do with cycles. But i am not very sure the strategy in drawing the graph to meet the requirement.

Answer 1

Your version of the Bellman-Ford algorithm will need as many iterations as the longest length (in edges) of all shortest paths in the graph.

Consider a directed graph with n vertices. You add edges 1 -> 2 -> 3 -> ... -> n to the graph, each having a small positive weight. Then you can add as many arbitrary heavy edges as you want. It is clear that the shortest path from 1 to n has length n-1. Thus your algorithm will need exactly n-1 iterations.

On further note, there is an improved version of the Bellman-Ford algorithm. It is called the Shortest Path Faster Algorithm. Although it has a worst-case run-time of O(|V|*|E|), which is the same as Bellman-Ford, very few graphs can make the algorithm reach that time. In practice, you can expect an average runtime of O(|E|) (unproven).