Bellman-Ford’s Algorithm in Python

The single-source shortest path problem is about finding the paths between a given vertex(called the source) to all the other vertices(called the destination) in a graph such that the total distance between them is minimum.

Bellman-Ford’s algorithm finds the shortest path between any two nodes of a given graph. While traversing the shortest path between two nodes, it is not necessary that every node will be visited.

Bellman-Ford’s algorithm is an example of Dynamic Programming. It starts with a starting vertex and calculates the distances of other vertices which can be reached by one edge. It then continues to find a path with two edges and so on. Bellman-Ford’s algorithm follows the bottom-up approach.

This algorithm takes a directed weighted graph and a starting vertex as input. It produces all the shortest paths from the starting vertex to all other vertices. Bellman-Ford’s Algorithm finds use in various real-life applications:

• Digital Mapping Services
• Social Networking Applications
• Telephone Network
• IP Routing to find the shortest path

Creation of Graph

To implement the Graph data structure, we first initialize the “Graph” class. Then, we overwrite the __init__ function and create another function to add weighted edges between the newly added nodes. The method print_solution will later be used to display the outcome of our algorithm.

#Initializing the Graph Class
class Graph:
    def __init__(self, vertices):
        self.V = vertices   
        self.graph = []     
        self.nodes = []

    def add_edge(self, s, d, w):
        self.graph.append([s, d, w])
    
    def addNode(self,value):
        self.nodes.append(value)

    def print_solution(self, dist):
        print("Distance of Vertex from Source")
        for key, value in dist.items():
            print('  ' + key, ' :    ', value)

Implementation of Bellman-Ford’s Algorithm to solve SSSP Problem

To implement Bellman-Ford’s algorithm in python, we create the bellmanFord method which takes the source point for the algorithm. Then, the distance between all destination points and the source point is calculated. During iteration, if a better path is found for the previous node, we use that particular path so as to improve the distance for further nodes.

Bellman-Ford’s algorithm is based on the following steps:

• We will receive a weighted graph and an initial source node.
• We need to traverse each node. Thus, we will visit each edge and try to reduce the path length of each seperate node.
• This process is repeated V times because it may take V iterations to find the shortest path length.
• Repeat this process until all the destination vertices have been assigned their path lengths.

#Implementing Bellman-Ford's Algorithm
def bellmanFord(self, src):
    dist = {i : float("Inf") for i in self.nodes}
    dist[src] = 0

    for temp in range(self.V-1):
        for s, d, w in self.graph:
            if dist[s] != float("Inf") and dist[s] + w < dist[d]:
                dist[d] = dist[s] + w
        
    for s, d, w in self.graph:
        if dist[s] != float("Inf") and dist[s] + w < dist[d]:
            print("Graph contains negative cycle")
            return
        

    self.print_solution(dist)

g = Graph(5)
g.addNode("A")
g.addNode("B")
g.addNode("C")
g.addNode("D")
g.addNode("E")
g.add_edge("A", "C", 6)
g.add_edge("A", "D", 6)
g.add_edge("B", "A", 3)
g.add_edge("C", "D", 1)
g.add_edge("D", "C", 2)
g.add_edge("D", "B", 1)
g.add_edge("E", "B", 4)
g.add_edge("E", "D", 2)
g.bellmanFord("E")

Output

Time and Space Complexity

The time complexity for Bellman-Ford’s algorithm is O(EV) where “V” is the number of vertices and “E” is the number of edges of the graph. This is due to the fact that we have used two loops nested together, one iterating over the vertices and the other iterating over the edges. The space complexity is O(V) because we need a temporary data structure to hold the vertices during the execution of the algorithm.

BFS vs Dijkstra vs Bellman-Ford

Graph Type	BFS	Dijkstra	Bellman-Ford
Unweighted-undirected	OK	OK	OK
Unweighted-directed	OK	OK	OK
Positive-weighted-undirected	X	OK	OK
Positive-weighted-directed	X	OK	OK
Negative-weighted-undirected	X	OK	OK
Negative-weighted-directed	X	OK	OK
Negative Cycle	X	X	OK