Bellman Ford Algorithm in Python

[2108 views]

There are plenty of algorithms to learn for getting better at programming. One such algorithm is the Bellman Ford algorithm that is used in the graph search. Let us know about it in detail.

What is the Bellman Ford Algorithm?

It is used for finding the shortest path between a source vertex to all the other vertices in a weighted digraph. However, the Bellman Ford Algorithm can also be used for the unweighted graph. It is basically known as the path-finding algorithm and sometimes as Bellman–Ford–Moore algorithm.

There is a similar algorithm known as the Dijikstras algorithm but Bellman Ford Algorithm is better in terms of versatility. The only issue is that it is a little slow but it can handle the graphs having negative edge weights. Negative edge weights have various uses in graphs.

The first proposal of this algorithm was given by Alfonso Shimbel in 1955. It is named after Richard Bellman and Lester Ford Jr in 1958 and 1959. It was published again by Edward F. Moore in 1957.

This algorithm uses graph data structure as it solves the weighted graph search problem. It has many applications like in calculating the shortest distance between two locations in Google Maps, distance vector routing protocol, and so on.

Python Implementation

Let A is the source vertex. In the first step, it is initialized that the distance is infinite excluding the distance to the source. As the total numbers of edges are 5 so they will be processed for 4 times.

Assuming that all the edges are processed in the following order: (B, E), (D, B), (B, D), (A, B), (A, C), (D, C), (B, C), (E, D), we will get the given distances. The first row is showing initial distance, the second row is showing the distance when edges (B, E), (D, B), (B, D) and (A, B) are dealt with, and the third row is showing the distances after processing (A, C). The last row is showing distance after processing (D, C), (B, C) and (E, D).

From the first iteration, you will get the shortest path of at most 1 edge long. When the edges will be processed for the second time then you will get the give distances. Similarly, the second iteration provides the shortest path at most 2 edges long. All edges are processed twice and distances are reduced after the second iteration gets over. Assuming that all the edges are processed in the following order: (B, E), (D, B), (B, D), (A, B), (A, C), (D, C), (B, C), (E, D), we will get the given distances. The first row is showing initial distance, second row is showing the distance when edges (B, E), (D, B), (B, D) and (A, B) are dealt with, and the third row is showing the distances after processing (A, C). The last row is showing distance after processing (D, C), (B, C) and (E, D).

from collections import defaultdict class Graph: def initial(self, vertices): self.V = vertices # No. of vertices self.graph = [] # default dictionary to store graph def add(self, u, v, w): self.graph.append([u, v, w]) def printsol(self, dist): print("Vertex Distance from Source") for i in range(self.V): print("% d \t\t % d" % (i, dist[i])) def BellmanFord(self, src): dist = [float("Inf")] * self.V dist[src] = 0 for i in range(self.V - 1): for u, v, w in self.graph: if dist[u] != float("Inf") and dist[u] + w < dist[v]: dist[v] = dist[u] + w for u, v, w in self.graph: if dist[u] != float("Inf") and dist[u] + w < dist[v]: print "Graph contains negative weight cycle" return self.printArr(dist) g = Graph(5) g.addEdge(0, 1, -1) g.addEdge(0, 2, 4) g.addEdge(1, 2, 3) g.addEdge(1, 3, 2) g.addEdge(1, 4, 2) g.addEdge(3, 2, 5) g.addEdge(3, 1, 1) g.addEdge(4, 3, -3) g.BellmanFord(0)