Bellman-Ford Algorithm: Pseudocode, Time Complexity and Examples

The Bellman-Ford Algorithm is a well-known algorithm in computer science that finds the shortest path from a source node to all other nodes in a weighted graph. It is capable of handling negative-weight edges. So, it is useful in computer networks and other networking applications. The algorithm is based on the idea of relaxation. Relaxation updates the shortest known distance for each vertex. In this blog, you will learn about the Bellman-Ford Algorithm, the steps to implement it, and a real-life example.

Table of Contents:

• What is Bellman-Ford Algorithm?
• How the Bellman-Ford Algorithm Works?
• Bellman-Ford Algorithm Example
• Pseudocode of Bellman-Ford Algorithm
• Code Implementations
• Complexity Analysis of Bellman-Ford Algorithm
• Difference Between Bellman-Ford and Dijkstra’s Algorithm
• Applications of Bellman-Ford Algorithm
• Best Practices for Bellman-Ford Implementation
• Conclusion

What is Bellman-Ford Algorithm?

In computer science, the Bellman-Ford algorithm is one of the most popular algorithms that is used for finding the shortest path. Bellman-Ford algorithm in Computer Networks is used to find the shortest path from a single source node to all other nodes in a weighted graph. This algorithm is named after Richard Bellman and Lester Ford, who invented this algorithm. It is useful in cases when a graph contains negative-weight edges

Unlock Python: Power Up Your Programming Skills!

Dive into real-world coding projects and become confident in writing clean, efficient Python code

Explore Program

How the Bellman-Ford Algorithm Works?

The Bellman-Ford algorithm works on the concept called relaxation, which means updating the shortest distance of every vertex step by step.

Let us understand the working of the Bellman-Ford algorithm:

Step 1: Start with a source vertex.

Step 2: Set the distance to the source as 0 and all other vertices as infinity.

Step 3: For each edge, check if the distance to the destination can be made shorter by going through another vertex.

Step 4: Repeat this process for all vertices (V-1) times, where V is the number of vertices.

Step 5: Finally, check for negative weight cycles. If any distance can still be reduced, then the graph contains a negative cycle.

The Bellman-Ford algorithm repeats the process several times to make sure that every shortest path is correctly found.

Input and Procedure

To apply the Bellman-Ford algorithm, we need:

1. A set of nodes (vertices)
2. A list of edges, each containing a starting vertex, an ending vertex, and a weight.
3. A source vertex from which we want to find the shortest paths.

Now, let us understand the procedure:

Step 1: Initialization

Initialize the distance from the source vertex to itself as 0, and set the distance to all other vertices as infinity.

Step 2: Relaxation

• Check if the distance to vertex v can be made shorter by going through the vertex u for edge (u,v).
• If yes, then update the distance of v.
• Repeat step 2 for all edges (V – 1) times.

Step 3: Check for Negative Weight Cycles

Check all the edges again, and if any distance can still be reduced, then there is a negative-weight cycle in the graph.

Bellman-Ford Algorithm Example

Let us understand the Bellman-Ford algorithm with the help of an example:

The above graph has five vertices (1 to 5), and with the help of the Bellman-Ford algorithm, we will find the shortest distance from the source vertex 1 to every other vertex.

Step 1: Initialization

Initially, the distance to the vertex at the source(1) is set to 0, and all the other vertices are set to infinity as they are not reachable yet.

Step 2: Relaxation

There are 5 vertices, so in step 2, we will relax all the edges 4 times (V-1=4).

This step helps in checking a shorter path through another vertex.

Iteration 1

1. 1 => 2 with weight 6 => distance(2) = 0 + 6 = 6
2. 1 => 3 with weight 5 => distance(3) = 0 + 5 = 5
3. 2 => 4 with weight -1 => distance(4) = 6 – 1 = 5
4. 3 => 2 with weight -2 => distance(2) = min(6, 5 – 2) = 3
5. 3 => 4 with weight 4 => distance(4) = min(5, 5 + 4) = 5
6. 3 => 5 with weight 3 => distance(5) = 5 + 3 = 8
7. 4 => 5 with weight 3 => distance(5) = min(8, 5 + 3) = 8

Iteration 2

1. 3 => 2 = -2 => no improvement (distance 2 stays 3)
2. 2 => 4 = -1 => distance(4) = min(5, 3 – 1) = 2
3. 4 => 5 = 3 => distance(5) = min(8, 2 + 3) = 5

Iteration 3:

No shorter paths are found. Distances remain the same.

Iteration 4:

Again, no changes, so the distances are final.

Step 3: Check for Negative Weight Cycles

Run one more iteration, and if any distance changes, then a negative weight cycle exists. Here, there is no change in the distances, so this graph does not contain any negative-weight cycle.

Final Shortest Distance Result

Explanation:

1. The algorithm originates at vertex 1 and successively checks all edges several times to update all distances.
2. Negative weights (such as -1 and -2) are handled without issues with the help of the relaxation technique.
3. On each pass, all the shortest paths have been updated correctly.
4. At the end of the process, the shortest distance from vertex 1 to all other vertices was computed to be [0, 3, 5, 2, 5].
5. The algorithm also verifies that there is no negative weight cycle.

Pseudocode of Bellman-Ford Algorithm

Let us have a look at the Pseudocode of the Bellman-Ford algorithm:

def BellmanFord(Edges, src, V):
    INF = 999999999
    dis = [INF] * V
    dis[src] = 0

    for _ in range(V - 1):
        for edge in Edges:
            u, v, wt = edge
            dis[v] = min(dis[v], dis[u] + wt)

    for edge in Edges:
        u, v, wt = edge
        if dis[v] > dis[u] + wt:
            print("Negative Weight cycle exists.")

    return dis

Here, the INF denotes infinity.

Code Implementations

Let us have a look at the implementation of the Bellman-Ford algorithm with different programming languages:

1. C/C++ Implementation of Bellman-Ford

Here is how the Bellman-Ford algorithm in C works:

#include <vector>
#include <climits>
using namespace std;

vector<int> bellmanFord(vector<vector<int>> edges, int src, int V) {
    vector<int> dis(V, INT_MAX);
    dis[src] = 0;

    for (int i = 0; i < V - 1; i++) {
        for (int j = 0; j < edges.size(); j++) {
            int u = edges[j][0];
            int v = edges[j][1];
            int wt = edges[j][2];
            if (dis[u] != INT_MAX && dis[v] > dis[u] + wt)
                dis[v] = dis[u] + wt;
        }
    }

    for (int j = 0; j < edges.size(); j++) {
        int u = edges[j][0];
        int v = edges[j][1];
        int wt = edges[j][2];
        if (dis[u] != INT_MAX && dis[v] > dis[u] + wt)
            return {}; // Negative cycle detected
    }

    return dis;
}

2. Java Implementation of Bellman-Ford

Here is how the Bellman-Ford algorithm in Java works:

import java.util.Arrays;

int[] bellmanFord(int[][] edges, int V, int src) {
    int[] dis = new int[V];
    Arrays.fill(dis, Integer.MAX_VALUE);
    dis[src] = 0;

    for (int i = 0; i < V - 1; i++) {
        for (int j = 0; j < edges.length; j++) {
            int u = edges[j][0];
            int v = edges[j][1];
            int wt = edges[j][2];
            if (dis[u] != Integer.MAX_VALUE && dis[u] + wt < dis[v])
                dis[v] = dis[u] + wt;
        }
    }

    for (int j = 0; j < edges.length; j++) {
        int u = edges[j][0];
        int v = edges[j][1];
        int wt = edges[j][2];
        if (dis[u] != Integer.MAX_VALUE && dis[u] + wt < dis[v])
            return new int[0]; // Negative cycle detected
    }

    return dis;
}

3. Python Implementation of Bellman-Ford

Here is how the Bellman-Ford algorithm in Java works:

def bellmanFord(V, edges, src):
    INF = 999999999
    dis = [INF] * V
    dis[src] = 0

    for _ in range(V - 1):
        for u, v, wt in edges:
            if dis[u] != INF and dis[u] + wt < dis[v]:
                dis[v] = dis[u] + wt

    for u, v, wt in edges:
        if dis[u] != INF and dis[u] + wt < dis[v]:
            return []  # Negative cycle detected

    return dis

Complexity Analysis of Bellman-Ford Algorithm

Complexity means how fast the algorithm runs(time) and how much memory it uses(space). Let us look at the time and space complexity of the Bellman-Ford algorithm:

1. Bellman-Ford Algorithm Time Complexity:

Understanding the time complexity of the Bellman-Ford algorithm helps in evaluating its performance for different graph sizes.

Given a graph with V vertices and E edges:

• It performs edge investigations V-1 times.
• Checking all edges once takes E time.

So, the total time = (V – 1) x E = O(V x E)

2. Bellman-Ford Algorithm Space Complexity:

There is no extra memory used apart from edges, in which we store the distance from the source to reach a vertex in an array of size V.

So, space complexity is:  O(V)

Difference Between Bellman-Ford and Dijkstra’s Algorithm

In the table below, you will understand Bellman-Ford algorithm vs Dijkstra algorithm:

Applications of Bellman-Ford Algorithm

Let us explore some important applications where this algorithm is used:

1. Networking and Routing

• It is one of the most popular uses of this algorithm in computer networks. It helps in finding the shortest path for packets of data from one computer to another. The Bellman-Ford algorithm in networking helps routers determine the shortest path to transfer data efficiently.

2. GPS Navigation

• The GPS systems also use shortest path algorithms in the search for the best route.
• The Bellman-Ford algorithm is used to calculate the paths when roads have negative costs(toll discounts or decreased time rate).

3. Robotics and Urban Planning

•  In the field of robotics, robots may need to traverse a grid or a map with obstacles.
• Bellman-Ford helps in calculating the shortest and safest path to reach a destination.
• Planning for the roads and transportation routes frequently involves planners using Bellman-Ford in an efficient manner.

Best Practices for Bellman-Ford Implementation

1. Proper Data Structures: Use arrays or lists to store edges and distances. This allows you to easily iterate and update.
2. Handle Negative Weights Carefully: Always check for negative weight cycles after running the algorithm. This is important, as skipping this step can lead to the incorrect shortest path.
3. Early Termination: If no distances have been updated while iterating, completing all V-1 iterations is unnecessary. This saves time while working with large graphs.
4. 5. Evaluation on Various Graphs: Test your implementation against positive, negative, and mixed weight graphs, as well as graphs that include cycles, to check for correctness.
5. 6. Unreachable Node: Make sure that your code handles unreachable nodes by setting their distance to infinity.

Start Coding in Python for Free: No Experience Needed

Begin writing actual Python code through interactive, beginner-friendly modules completely for free.

Explore Program

Conclusion

The Bellman-Ford algorithm is a reliable method for finding shortest paths, even in graphs with negative weights. It will relax the edges to ensure that the shortest distances are computed correctly, and it will detect negative weight cycles, which many other algorithms, such as Dijkstra’s algorithm, cannot. The algorithm runs in time complexity of O(V × E) and space complexity of O(V), so it is suitable only for small to medium-sized graphs. The applications of this algorithm vary from networking, GPS navigation, robotics, logistics, and many more, which makes it an important algorithm for computer networks and real-life cases.

Bellman-Ford Algorithm – FAQs