Bellman-Ford Algorithm

Previous
Quiz
Next

Bellman-Ford is a popular algorithm for finding the shortest path from a starting point (or "source") to all other points in a graph, even if some edges have negative weights. While its not as fast as Dijkstras algorithm, it has a big advantage: it can handle graphs with negative edge weights.

How does Bellman-Ford work?

The way the Bellman-Ford algorithm works is pretty simple. It goes through all the edges of the graph multiple times and tries to improve the shortest path estimates. It "relaxes" the edges by updating the distances until they converge to the correct values.

It continues to do this for all edges in the graph, ensuring the optimal solution.

So, even though it might take a bit longer than Dijkstras, its a good tool when negative weights are involved!

Alogrithm steps for Bellman-Ford

Heres a step-by-step guide to how the Bellman-Ford algorithm works:

  • Initialization: Start by assigning a distance of 0 to the source node and infinity () to all other nodes.
  • Relaxation: Go through all the edges of the graph and relax them. Relaxing an edge means updating the distance of the destination node if a shorter path is found.
  • Repeat: Repeat the relaxation step for all edges in the graph. Keep doing this until no more improvements can be made.
  • Negative Cycle Detection: After the relaxation step, check for negative cycles. If there are negative cycles in the graph, the algorithm will detect them and report that there is no shortest path.

Code for Bellman-Ford Algorithm

Consider a simple graph with vertices and edges.

    (0)
    /   \
  10     15
  /       \
(1)---5---(3)  
  \       /
   10    10
    \   /
     (4)
       \
        10
         \
          (5)

Example

Here's an example code snippet for the Bellman-Ford Shortest Path algorithm in C, C++, Java, and Python:

C C++ Java Python 
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#define MAX_VERTICES 6

int graph[MAX_VERTICES][MAX_VERTICES] = {
   {0, 10, 0, 15, 0, 0},
   {0, 0, 0, 5, 10, 0},
   {0, 0, 0, 0, 0, 10},
   {0, 0, 0, 0, 0, 5},
   {0, 0, 0, 0, 0, 10},
   {0, 0, 0, 0, 0, 0}
};

void bellman_ford(int source) {
   int distance[MAX_VERTICES];

   for (int i = 0; i < MAX_VERTICES; i++) {
      distance[i] = INT_MAX;
   }
   distance[source] = 0;

   for (int i = 0; i < MAX_VERTICES - 1; i++) {
      for (int u = 0; u < MAX_VERTICES; u++) {
         for (int v = 0; v < MAX_VERTICES; v++) {
            if (graph[u][v] != 0 && distance[u] != INT_MAX && distance[u] + graph[u][v] < distance[v]) {
               distance[v] = distance[u] + graph[u][v];
            }
         }
      }
   }

   for (int u = 0; u < MAX_VERTICES; u++) {
      for (int v = 0; v < MAX_VERTICES; v++) {
         if (graph[u][v] != 0 && distance[u] != INT_MAX && distance[u] + graph[u][v] < distance[v]) {
            printf("Graph contains negative weight cycle\n");
            return;
         }
      }
   }

   printf("Vertex   Distance from Source\n");
   for (int i = 0; i < MAX_VERTICES; i++) {
      if (distance[i] == INT_MAX)
         printf("%d \t\t INF\n", i);
      else
         printf("%d \t\t %d\n", i, distance[i]);
   }
}

int main() {
   bellman_ford(0);
   return 0;
}

Output

Following is the output of the above code:

Vertex   Distance from Source
0 		 0
1 		 10
2 		 INF
3 		 15
4 		 20
5 		 20

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

#define MAX_VERTICES 6

int graph[MAX_VERTICES][MAX_VERTICES] = {
   {0, 10, 0, 15, 0, 0},
   {0, 0, 0, 5, 10, 0},
   {0, 0, 0, 0, 0, 10},
   {0, 0, 0, 0, 0, 5},
   {0, 0, 0, 0, 0, 10},
   {0, 0, 0, 0, 0, 0}
};

void bellman_ford(int source) {
   int distance[MAX_VERTICES];

   for (int i = 0; i < MAX_VERTICES; i++) {
      distance[i] = INT_MAX;
   }
   distance[source] = 0;

   for (int i = 0; i < MAX_VERTICES - 1; i++) {
      for (int u = 0; u < MAX_VERTICES; u++) {
         for (int v = 0; v < MAX_VERTICES; v++) {
            if (graph[u][v] != 0 && distance[u] != INT_MAX && distance[u] + graph[u][v] < distance[v]) {
               distance[v] = distance[u] + graph[u][v];
            }
         }
      }
   }

   for (int u = 0; u < MAX_VERTICES; u++) {
      for (int v = 0; v < MAX_VERTICES; v++) {
         if (graph[u][v] != 0 && distance[u] != INT_MAX && distance[u] + graph[u][v] < distance[v]) {
            cout << "Graph contains negative weight cycle" << endl;
            return;
         }
      }
   }

   cout << "Vertex   Distance from Source" << endl;
   for (int i = 0; i < MAX_VERTICES; i++) {
      if (distance[i] == INT_MAX)
         cout << i << " \t\t INF" << endl;
      else
         cout << i << " \t\t " << distance[i] << endl;
   }
}

int main() {
   bellman_ford(0);
   return 0;
}

Output

Following is the output of the above code:

Vertex   Distance from Source
0 		 0
1 		 10
2 		 INF
3 		 15
4 		 20
5 		 20

// Java program to find the shortest path from a source node to all other nodes using Bellman-Ford algorithm
import java.util.*;

public class Main {
   static final int MAX_VERTICES = 6;
   static int[][] graph = {
      {0, 10, 0, 15, 0, 0},
      {0, 0, 0, 5, 10, 0},
      {0, 0, 0, 0, 0, 10},
      {0, 0, 0, 0, 0, 5},
      {0, 0, 0, 0, 0, 10},
      {0, 0, 0, 0, 0, 0}
   };

   static void bellmanFord(int source) {
      int[] distance = new int[MAX_VERTICES];

      for (int i = 0; i < MAX_VERTICES; i++) {
         distance[i] = Integer.MAX_VALUE;
      }
      distance[source] = 0;

      for (int i = 0; i < MAX_VERTICES - 1; i++) {
         for (int u = 0; u < MAX_VERTICES; u++) {
            for (int v = 0; v < MAX_VERTICES; v++) {
               if (graph[u][v] != 0 && distance[u] != Integer.MAX_VALUE && distance[u] + graph[u][v] < distance[v]) {
                  distance[v] = distance[u] + graph[u][v];
               }
            }
         }
      }

      for (int u = 0; u < MAX_VERTICES; u++) {
         for (int v = 0; v < MAX_VERTICES; v++) {
            if (graph[u][v] != 0 && distance[u] != Integer.MAX_VALUE && distance[u] + graph[u][v] < distance[v]) {
               System.out.println("Graph contains negative weight cycle");
               return;
            }
         }
      }

      System.out.println("Vertex   Distance from Source");
      for (int i = 0; i < MAX_VERTICES; i++) {
         if (distance[i] == Integer.MAX_VALUE)
            System.out.println(i + " \t\t INF");
         else
            System.out.println(i + " \t\t " + distance[i]);
      }
   }

    public static void main(String[] args) {
        bellmanFord(0);
    }

}

Output

Following is the output of the above code:

Vertex   Distance from Source
0 		 0
1 		 10
2 		 INF
3 		 15
4 		 20
5 		 20

MAX_VERTICES = 6

graph = [
   [0, 10, 0, 15, 0, 0],
   [0, 0, 0, 5, 10, 0],
   [0, 0, 0, 0, 0, 10],
   [0, 0, 0, 0, 0, 5],
   [0, 0, 0, 0, 0, 10],
   [0, 0, 0, 0, 0, 0]
]

def bellman_ford(source):
   distance = [float('inf')] * MAX_VERTICES
   distance[source] = 0

   for i in range(MAX_VERTICES - 1):
      for u in range(MAX_VERTICES):
         for v in range(MAX_VERTICES):
            if graph[u][v] != 0 and distance[u] != float('inf') and distance[u] + graph[u][v] 

Output


Following is the output of the above code:


Vertex   Distance from Source
0 		 0
1 		 10
2 		 INF
3 		 15
4 		 20
5 		 20

Time Complexity of Bellman-Ford Algorithm

  • The time complexity of the Bellman-Ford algorithm is O(V*E), where V is the number of vertices and E is the number of edges in the graph.
  • The algorithm goes through all the edges of the graph V-1 times, relaxing them to find the shortest path.
  • If there are no negative cycles in the graph, the algorithm will converge to the correct shortest path after V-1 iterations.

Applications of Bellman-Ford Algorithm

The Bellman-Ford algorithm is used in various applications, including:

  • Routing Protocols: Bellman-Ford is used in routing protocols like RIP (Routing Information Protocol) to find the shortest path in computer networks.
  • Network Optimization: Its used in network optimization problems to find the shortest path between two points in a graph.
  • Resource Allocation: Bellman-Ford is used in resource allocation problems to find the most efficient way to allocate resources.
  • Graph Analysis: Its used in graph analysis to find the shortest path between two nodes in a graph.

Conclusion

In this tutorial, we learned about the Bellman Ford Shortest Path algorithm. It's code, time complexity, and applications.

Print Page
Previous
Next
Advertisements