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

C++

Java

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

1 × four =