# 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])

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)