BellmanFord Algorithm
General Purpose Shortest Paths Algorithm which can handle both Negative Weight Edges and Positive Cycles, and can detect existence of Negative Cycle. Time Complexity: O(EV). Space Complexity: O(V)

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.
There are a lot of practical realworld problems that would require us to have both (1) cycle, and (2) negative weight edges in a directed graph at the same time. Sometimes it would also require us to detect if there is a negative cycle in a graph. These are not just theoretical concepts, rather they exist because we do need them to solve real problems. One of the realworld problem called Arbitrage that we would discuss in our next chapter, exhibits the necessity of all of these: cycles, negative weight edges, and negative cycles. This is why we need BellmanFord Algorithm.
We have already seen that Dijkstra's Algorithm can handle cycles but not negative weight edges. On the other hand Topological Sort w/ Vertex Relaxation Approach works fine for negative weight edges but not when there is a cycle in the given graph. This is where BellmanFord Algorithm stand out. BellmanFord Algorithm can handle presence of both cycles and negative weight edges at the same time. As we have mentioned before that graphs with negative cycle (cycles for which the sum of the weights of the edges is negative) is an illposed problem for finding shortest paths, because you can just spin around the cycle to generate arbitrarily shorter paths. So definitely, we cannot find shortest paths using BellmanFord if there is any negative cycle in the graph. But what is great about BellmanFord Algorithm is that it can help us in identifying if a graph has a negative cycle.
Prerequisites:
BellmanFord Algorithm returns a boolean value indicating whether or not there is a negativeweight cycle that is reachable from the source. If there is such a cycle, the algorithm indicates that no solution exists. If there is no such cycle, the algorithm produces the shortest paths and their weights.
BellmanFord Algorithm works as below when our goal is to find shortest paths from source vertex to all other vertices in a directed graph:

Initialize distance[source] = 0
and
distance[i] = INFINITY for all vertices i which are not source. 
Consider all the edges in any order and relax them, and by that I mean, Do vertex relaxation in any order.
Repeat this for a total of (V  1) times, where V = total number of vertices in the given directed graph.  Check for existence of any negative cycle that is reachable from the source vertex.
Why do we run the loop for (V  1) times relaxing all the edges ?
When we are looking for shortest paths, if a graph has V number of vertices then the longest such path without a cycle can have all the V vertices, at the maximum. Consequently, such path will have (V  1) edges.Since the longest possible path without a cycle can be (V  1) edges, the edges must be scanned (V  1) times to ensure the shortest path has been found for all nodes. That is why we iterate the loop for (V  1) times.
Let's consider the below graph where the shortest path from A to D is A > B > C > D and let's see why repeating for (V  1) loops actually guarantee computing the shortest paths correctly:
A > B > C > D
We will have to keep in mind that we can do edge relaxation in any order. So for the graph above, if we relax the vertex in the order A > B > C > D then we would get the shortest path in the first iteration, and in the subsequent iteration there will be no updation. However, if we scan the vertices in the order D, C, B and A, then it would take 3 iterations to actually get the shortest path, because in the first iteration only AB edge will be relaxed. In second iteration BC will be relaxed followed by CD in third iteration
How to check if there is any negative weight cycle in the graph ?
In the BellmanFord Algorithm the last step is looking for existence of a negative weight cycle. By the time we start looking for negative weight cycle we have already done edge relaxation and computed Shortest Paths. However, even if we have already computed the Shortest Paths, it adds no value if there is already at least one negative weight cycle in the graph. It is because shortest paths problems with a graph with negative weight cycles is an illposed problem and shortest paths cannot be found using BellmanFord Algorithm.So, in BellmanFord Algorithm after running the loop for (V  1) times and performing edge relaxations, a final scan of all the edges is performed and if any distance is updated, then a path of length V edges has been found which can only occur if at least one negative cycle exists in the graph. If there is a negative cycle, then you will find distance to at least one vertex is getting updated as the negative cycle will result in a shorter distance.
So, for a directed edge UV if the below holds true then there is a negative cycle:
distance[v] > distance[u] + weight[u][v]
Reason being, we have already computed all the shortest paths, and so we won't be expecting to get any path shorter than the ones already found. Only exception would be when we'd have a negative weight cycle in the given graph.
BellmanFord Algorithm:

Initialize distance[] and parent[] array. distance[i] stores shortest distance to vertex i from source. parent[i] stores
the vertex that preceeds immediately before vertex i in the shortest path from source to vertex i.
parent[source] = 1
distance[i] = POSITIVE INFINITY, for all i from 1 to (V  1), where V = total number of vertices in the graph, the vertices being 0 to (V  1).
distance[source] = 0 . 
for (i = 1 to (V  1)) { for each edge (u,v) present in the graph { relax edge (u, v); } }

for each edge (u,v) present in the graph { if (distance[v] > distance[u] + weight[u][v]) { return FALSE; } }
 return TRUE;
Code:
This is a Premium content. Please subscribe to access the code.
After subscribing please come back and refresh this page.
Time Complexity:
O(EV), since we making (V  1) loops and in each loop we are visiting all edges.
Like Dijkstra's algorithm, BellmanFord proceeds by relaxation, in which approximations to the correct
distance are replaced by better ones until they eventually reach the solution. In both algorithms, the
approximate distance to each vertex is always an overestimate of the true distance and is replaced by the
minimum of its old value and the length of a newly found path.
However, Dijkstra's algorithm uses a priority queue to greedily select the closest vertex that has not yet been processed, and performs this relaxation process on all of its outgoing edges; by contrast, the BellmanFord algorithm simply relaxes all the edges and does this ∣V∣−1 times, where ∣V∣ is the number of vertices in the graph. In each of these repetitions, the number of vertices with correctly calculated distances grows, from which it follows that eventually, all vertices will have their correct distances. This method allows the BellmanFord algorithm to be applied to a wider class of inputs than Dijkstra.
An important part to understanding the Bellman Ford's working is that at each step, the relaxations lead to the discovery of new shortest paths to nodes. After the first iteration over all the vertices, AT THE VERY LEAST the algorithm finds out all the shortest paths from the source to nodes which can be reached with one hop (one edge). Similarly, after the (K + 1)th step, BellmanFord Algorithm GUARANTEES finding the shortest distances for all the nodes that can be reached from the source using a maximum of K hops (having K edges).
However, Dijkstra's algorithm uses a priority queue to greedily select the closest vertex that has not yet been processed, and performs this relaxation process on all of its outgoing edges; by contrast, the BellmanFord algorithm simply relaxes all the edges and does this ∣V∣−1 times, where ∣V∣ is the number of vertices in the graph. In each of these repetitions, the number of vertices with correctly calculated distances grows, from which it follows that eventually, all vertices will have their correct distances. This method allows the BellmanFord algorithm to be applied to a wider class of inputs than Dijkstra.
An important part to understanding the Bellman Ford's working is that at each step, the relaxations lead to the discovery of new shortest paths to nodes. After the first iteration over all the vertices, AT THE VERY LEAST the algorithm finds out all the shortest paths from the source to nodes which can be reached with one hop (one edge). Similarly, after the (K + 1)th step, BellmanFord Algorithm GUARANTEES finding the shortest distances for all the nodes that can be reached from the source using a maximum of K hops (having K edges).
Problem Solving:
There are n cities connected by m flights. Each flight starts from city u and arrives at v with a price w.Now given all the cities and flights, together with starting city src and the destination dst, your task is to find the cheapest price from src to dst with up to k stops. If there is no such route, output 1.
Example 1:
Input:
n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
src = 0, dst = 2, k = 1
Output: 200
The cheapest price from city 0 to city 2 with at most 1 stop costs 200.
Example 2:
Input:
n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
src = 0, dst = 2, k = 0
Output: 500
Explanation:
The cheapest price from city 0 to city 2 with at most 0 stop costs 500.
Solution:
Carefully see how BellmanFord Algorithm has been used to solve this problem. Please see the comments.This is a Premium content. Please subscribe to access the code.
After subscribing please come back and refresh this page.
Time Complexity:
We have a loop which has (K+1) iterations and in each loop we visit O(E) edges, where E = total number of edges (flight routes). In worst case E = V * V. So if there are N number of cities and K maximum allowed stops then overall time complexity is O(K * V * V).We will see more realworld application of BellmanFord Algorithm in Arbitrage chapter.
Related MustRead Topics:
 Dijkstra's Algorithm
 Longest Paths Algorithm
 BellmanFord Algorithm & Negative Cycle Detection
 Optimized BellmanFord
 Sequential Job Scheduling
 Parallel Job Scheduling

Parallel Job Scheduling
w/ Relative Deadlines  Arbitrage
The above content is written by:
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
If you have any feedback, please use this form: https://thealgorists.com/Feedback.
Follow Us On LinkedIn