Summary: In this tutorial, we’ll learn what the Bellman-Ford algorithm is, how it works, and how to find the cost of the path from the source vertex to all other vertices in a given graph using the algorithm in C++, Java, and Python.

Introduction to Bellman-Ford Algorithm

Bellman-Ford algorithm is a single source shortest path algorithm that finds the shortest path from the source vertex to all other vertices in a given weighted graph.

For example, if we run the Bellman-Ford algorithm with ‘A’ as the source vertex in the following graph, it will produce the shortest distance from the source vertex to all other vertices of the graph (vertex ‘B’ and ‘C’):

Shortest Path using Bellman Ford Algorithm

The Belman algorithm works similar to Dijkstra’s algorithm, however, it can handle graphs with negative-weighted edges.

How the Bellman-Ford Algorithm Works?

Bellman-Ford algorithm starts with the initialization process. It initializes the distance of the starting vertex to zero (0) and all other vertices to positive infinity (∞) because the distance from the starting vertex to itself is zero.

initializing vertex distance

After initialization, the algorithm relaxes all the edges of the graph |V-1| times.

Relaxing means trying to lower the cost of getting to a vertex by using another vertex.

Relaxing the edges of the graph

After the relaxation process, the algorithm examines the last time whether any edge can be relaxed further? If so this means that the graph has a negative cycle, otherwise the distance of any vertex is the distance from the source vertex to that vertex.

Why Each Edge is Relaxed |V-1| Times?

In any given graph, the shortest path between two any two vertices can include a maximum of V vertices (i.e. all the vertices of the graph), and any simple path with a V number of vertices cannot have more than V-1 edges.

Also, like other Dynamic Programming Problems, the Bellman-Ford algorithm finds the shortest paths in a bottom-up manner. It first calculates the shortest distances which have at-most one edge in the path. Then, it calculates the shortest paths with at-most 2 edges, and so on.

Hence, assuming there is no negative cycle in the graph, the Bellman-Ford algorithm treats the search as the worst case and iterates over the edges V-1 times to guarantee the solution.

Implementation of Bellman-Ford Algorithm

Bellman-Ford algorithm in any programming language can be implemented by following the following steps:

  1. Set the distance of the source vertex to 0 and of all other vertices to +∞.
  2. Loop |V-1| times.
    1. Relax all the edges of the graph.
  3. Try relaxing all the edges one more time.
    1. If any edge can be relaxed, then it means the given graph has a negative cycle.
  4. Otherwise, output the distance of the vertices.

Here is the implementation of the algorithm in C++, Java and Python:

Python

class Vertex:
  def __init__(self, name):
    #vertex label
    self.name = name
    #distance from the source vertex
    self.distance = float('inf') 

class Edge:
  def __init__(self, _from, _to, _cost):
    #from vertex
    self._from = _from
    #to vertex
    self._to = _to
    #edge weight or cost
    self._cost = _cost

class BellmanFord:
  #method implementing Bellman Ford algorithm
  def findPath(self, source, edges, v):
    #distance of the source vertex to itself is 0
    source.distance = 0

    #relax all the edges V-1 times
    for i in range(v-1):
      for edge in edges:
        if edge._from.distance + edge._cost < edge._to.distance:
          edge._to.distance = edge._from.distance + edge._cost

    #If any more relaxation is possible
    #then, it means graph has a cycle
    for edge in edges:
        if edge._from.distance + edge._cost < edge._to.distance:
          print("Graph has a negative cycle")
          return False

    return True

if __name__ == '__main__':
  #vertices of the graph
  vertices = [Vertex('A'), Vertex('B'), Vertex('C')]
  #edges of the graph
  edges = [Edge(vertices[0], vertices[1], 10), 
           Edge(vertices[1], vertices[2], 10),
           Edge(vertices[0], vertices[2], 30)]

  #driver code
  bellmanFord = BellmanFord()
  
  if bellmanFord.findPath(vertices[0], edges, len(vertices)):
    #output the distance of the vertices
    for vertex in vertices:
      print(f"A->{vertex.name}: {vertex.distance}")

C++

#include <iostream>
#include <limits>
#include <list>
using namespace std;

class Vertex{
public:
  //vertex label
  char name;
  //distance from the source vertex
  double distance; 

  Vertex(char name){
    this->name = name;
    this->distance = numeric_limits<double>::infinity();
  }
};

class Edge{
public:
  //from vertex
  Vertex* from;
  //to vertex
  Vertex* to;
  //edge weight or cost
  double cost;

  Edge(Vertex *from, Vertex* to, double cost){
    this->from = from;
    this->to = to;
    this->cost = cost;
  }
};

class BellmanFord{
public:
  //method implementing Bellman Ford algorithm
  bool findPath(Vertex* source, list<Edge*> edges, int v){
    //distance of the source vertex to itself is 0
    source->distance = 0;

    //relax all the edges V-1 times
    for(int i=1; i<=(v-1); i++){
      for(Edge* edge: edges){
        if(edge->from->distance + edge->cost < edge->to->distance)
          edge->to->distance = edge->from->distance + edge->cost;
      }
    }

    //If any more relaxation is possible
    //then, it means graph has a cycle
    for(Edge* edge: edges){
      if(edge->from->distance + edge->cost < edge->to->distance){
        cout << "Graph has a negative cycle";
        return false;
      }
    }

    return true;
  }
};

int main() {
  //vertices of the graph
  Vertex* vertices[] = {new Vertex('A'), new Vertex('B'), new Vertex('C')};
  //edges of the graph
  list<Edge*> edges {new Edge(vertices[0], vertices[1], 10), 
                 new Edge(vertices[1], vertices[2], 10),
                 new Edge(vertices[0], vertices[2], 30)};
  //driver code
  BellmanFord bellmanFord;
  
  if(bellmanFord.findPath(vertices[0], edges, 3))
    //output the distance of all the vertex
    for(Vertex* vertex: vertices){
      cout << "A->" << vertex->name << ": " << vertex->distance << "\n";
    }
}

Java

import java.util.*;

class Vertex{
  //vertex label
  char name;
  //distance from the source vertex
  double distance; 

  Vertex(char name){
    this.name = name;
    this.distance = Double.POSITIVE_INFINITY;
  }
}

class Edge{
  //from vertex
  Vertex from;
  //to vertex
  Vertex to;
  //edge weight or cost
  double cost;

  Edge(Vertex from, Vertex to, double cost){
    this.from = from;
    this.to = to;
    this.cost = cost;
  }
}

class BellmanFord{
  //method implementing Bellman Ford algorithm
  boolean findPath(Vertex source, Edge edges[], int v){
    //distance of the source vertex to itself is 0
    source.distance = 0;

    //relax all the edges V-1 times
    for(int i=1; i<=(v-1); i++){
      for(Edge edge: edges){
        if(edge.from.distance + edge.cost < edge.to.distance)
          edge.to.distance = edge.from.distance + edge.cost;
      }
    }

    //If any more relaxation is possible
    //then, it means graph has a cycle
    for(Edge edge: edges){
      if(edge.from.distance + edge.cost < edge.to.distance){
        System.out.println("Graph has a negative cycle");
        return false;
      }
    }

    return true;
  }
}

class Main {
  public static void main(String[] args) {
    //vertices of the graph
  Vertex vertices[] = {new Vertex('A'), new Vertex('B'), new Vertex('C')};
  //edges of the graph
  Edge edges[] = {new Edge(vertices[0], vertices[1], 10), 
                 new Edge(vertices[1], vertices[2], 10),
                 new Edge(vertices[0], vertices[2], 30)};
  //driver code
  BellmanFord bellmanFord = new BellmanFord();
  
  if(bellmanFord.findPath(vertices[0], edges, 3))
    //output the distance of all the vertex
    for(Vertex vertex: vertices){
       System.out.println("A->"+vertex.name+": "+ vertex.distance);
    }
  }
}

Output:

A->A: 0
A->B: 10
A->C: 20


In our example, there were no negative edges in the graph, so we successfully found the distance of each vertex from the source vertex.

Overview of the Bellman-Ford Algorithm

  • The Bellman-Ford algorithm|V-1| times relaxes every edge of the graph, hence the time complexity of the algorithm is O(VE).
  • Bellman-Ford algorithm can also work with a non-negative undirected graph, but it can only handle negative edges in a directed graph.
  • The algorithm often used for detecting negative cycles in a directed graph.

In this tutorial, we learned what the Bellman-Ford algorithm is, how it works, and how to implement Bellman-Ford algorithm in C++, Java, and Python to find the cost of the path.

Leave a Reply

19 − eleven =