Bellman-Ford 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)


There are a lot of practical real-world 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 real-world 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 Bellman-Ford 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 Bellman-Ford Algorithm stand out. Bellman-Ford 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 ill-posed 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 Bellman-Ford if there is any negative cycle in the graph. But what is great about Bellman-Ford Algorithm is that it can help us in identifying if a graph has a negative cycle.

Pre-requisites:
  1. Topological Sort w/ Vertex Relaxation Approach
  2. Finding Longest Paths Using Topological Sort


Bellman-Ford Algorithm returns a boolean value indicating whether or not there is a negative-weight 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.

Bellman-Ford Algorithm works as below when our goal is to find shortest paths from source vertex to all other vertices in a directed graph:
  1. Initialize distance[source] = 0
    and
    distance[i] = INFINITY for all vertices i which are not source.
  2. 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.
  3. 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 Bellman-Ford 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 ill-posed problem and shortest paths cannot be found using Bellman-Ford Algorithm.
So, in Bellman-Ford 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.

Bellman-Ford Algorithm:
  1. 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 . 
  2.         
for (i = 1 to (V - 1)) {
    for each edge (u,v) present in the graph {
        relax edge (u, v);
    }
}
        
  3.         
for each edge (u,v) present in the graph {
    if (distance[v] > distance[u] + weight[u][v]) {
         return FALSE;
    }
}
  4. return TRUE;


Code:



Login to Access Content


Time Complexity:

O(EV), since we making (V - 1) loops and in each loop we are visiting all edges.


Like Dijkstra's algorithm, Bellman-Ford 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 Bellman-Ford 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 Bellman-Ford 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, Bellman-Ford 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 Bellman-Ford Algorithm has been used to solve this problem. Please see the comments.
Java code:


Login to Access Content



Python code:


Login to Access Content




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 real-world application of Bellman-Ford Algorithm in Arbitrage chapter.


Related Must-Read Topics:

  1. Dijkstra's Algorithm
  2. Longest Paths Algorithm
  3. Bellman-Ford Algorithm & Negative Cycle Detection
  4. Optimized Bellman-Ford
  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