Optimized BellmanFord Algorithm

Algorithms and Data Structures: TheAlgorist.com

System Design: www.System.Design

Low Level Design: LowLevelDesign.io

Frontend Engineering: FrontendEngineering.io
জয় শ্রী রাম
🕉
Prerequisite: BellmanFord Algorithm & Negative Cycle Detection
In the previous chapter while studying BellmanFord 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.
Login to Access Content
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 BellmanFord 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 nonempty after the V^{th} pass through all the edges.Related Chapters:
 Dijkstra's Algorithm
 Longest Paths Algorithm
 Topological Sort w/ Vertex Relaxation
 BellmanFord Algorithm & Negative Cycle Detection
 Sequential Job Scheduling
 Parallel Job Scheduling

Parallel Job Scheduling
w/ Relative Deadlines  Arbitrage