• Customer Support: admin@thealgorists.com
  • Feedback: We are listening to your every feedback, and taking action to constantly improve your learning experience. If you have any feedback, please use this form: https://thealgorists.com/Feedback.
  • If you are a student, email to admin@thealgorists.com to get special student discount.



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 access the code.
After subscribing please come back and refresh this page.



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


The above content is written by:

Abhishek Dey

Abhishek Dey

A Visionary Software Engineer With A Mission To Empower Every Person & Every Organization On The Planet To Achieve More

Microsoft | University of Florida

View LinkedIn profile


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




Subscribe to Our Youtube Channel

Follow Us On LinkedIn
wave