Optimized Bellman-Ford Algorithm


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.



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 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.


Related Chapters:

  1. Dijkstra's Algorithm
  2. Longest Paths Algorithm
  3. Topological Sort w/ Vertex Relaxation
  4. Bellman-Ford Algorithm & Negative Cycle Detection
  5. Sequential Job Scheduling
  6. Parallel Job Scheduling
  7. Parallel Job Scheduling
    w/ Relative Deadlines
  8. Arbitrage


Instructor:

Abhishek Dey

Abhishek Dey

Senior SDE | Chief Architect

Microsoft | University of Florida

View LinkedIn profile


If you have any feedback, please use this form: https://thealgorists.com/Feedback.


Help Your Friends save 40% on our products

wave