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’):
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.
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.
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:
- Set the distance of the source vertex to 0 and of all other vertices to +∞.
- Loop |V-1| times.
- Relax all the edges of the graph.
- Try relaxing all the edges one more time.
- If any edge can be relaxed, then it means the given graph has a negative cycle.
- Otherwise, output the distance of the vertices.
Here is the implementation of the algorithm in C++, Java and Python:
Python
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 | 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++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 | #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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 | 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: 0A->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.