Optimized Bellman-Ford Algorithm
Algorithms and Data Structures: TheAlgorist.com
System Design: DistributedComputing.dev
Low Level Design: LowLevelDesign.io
Frontend Engineering: FrontendEngineering.io
Pre-requisite: Bellman-Ford Algorithm & Negative Cycle Detection
In the previous chapter while studying Bellman-Ford Algorithm we saw that in every iteration we are considering all the edges and trying to relax them. But, if we give it a little bit thought we would notice that in every iteration we would need to relax only those vertices for which at least one of the inbound edges had gotten relaxed in the previous iteration. What I mean here is, if distance[vertex] was not updated in the previous iteration, then we should not relax this vertex in the current iteration. So, as an optimization we would keep a queue just to keep track of this.
This is a Premium content.
Please subscribe to Algorithms course to access the code.
Time Complexity:O(EV), where E = number of edges in the graph and V = number of vertices in the graph.
Note:If there is no negative cycle reachable from source, the algorithm terminates after relaxations corresponding to the (V - 1) pass of the generic Bellman-Ford algorithm. If there is a negative weight cycle reachable from source then the queue we are using in this optimized algorithm never empties. If we do not have the check for finding negative cycle in each iteration in our implementation, then the digraph has a negative cycle reachable from the source if and only of the queue is non-empty after the Vth pass through all the edges.
- Dijkstra's Algorithm
- Longest Paths Algorithm
- Topological Sort w/ Vertex Relaxation
- Bellman-Ford Algorithm & Negative Cycle Detection
- Sequential Job Scheduling
- Parallel Job Scheduling
Parallel Job Scheduling
w/ Relative Deadlines
Senior SDE | Chief Architect
Microsoft | University of Florida
If you have any feedback, please use this form: https://thealgorists.com/Feedback.