Implementing the Bellman-Ford Algorithm in Python

The Bellman-Ford algorithm is a well-known algorithm for finding the shortest path from a single source vertex to all other vertices in a weighted graph. Unlike Dijkstra’s algorithm, Bellman-Ford can handle graphs with negative edge weights, making it more versatile, though slightly less efficient. In this blog, we’ll dive into the Bellman-Ford algorithm, understand how it works, and implement it step by step in Python.

What is the Bellman-Ford Algorithm?

The Bellman-Ford algorithm computes the shortest paths from a single source vertex to all other vertices in a graph. The key advantage of Bellman-Ford is its ability to handle graphs with negative edge weights, which Dijkstra’s algorithm cannot do. However, Bellman-Ford does not work with graphs containing negative weight cycles (cycles whose edges sum to a negative number).

How Does the Bellman-Ford Algorithm Work?

The algorithm iteratively relaxes the edges of the graph, meaning it checks if the shortest known distance to a vertex can be improved by taking a specific edge. The process is repeated |V| - 1 times, where |V| is the number of vertices in the graph. If after |V| - 1 iterations, any edge can still be relaxed, the graph contains a negative weight cycle.

Bellman-Ford Algorithm Steps:

1. Initialize distances: Set the distance to the source vertex to 0 and all others to infinity.

2. Relax edges: For each edge, update the distance if a shorter path is found.

3. Detect negative cycles: Check if a shorter path is found after |V| - 1 iterations. If so, a negative cycle exists.

Bellman-Ford Algorithm Implementation in Python

Let’s implement the Bellman-Ford algorithm step by step.

class Graph:

     def init(self, vertices):

         self.V = vertices # Number of vertices in the graph

         self.edges = [] # List to store graph edges

     def add_edge(self, u, v, w):

        self.edges.append((u, v, w))

     def bellman_ford(self, src):

         # Step 1: Initialize distances from src to all other vertices as INFINITE

         dist = [float('inf')] * self.V

         dist[src] = 0

         # Step 2: Relax all edges |V| - 1 times

         for _ in range(self.V - 1):

             for u, v, w in self.edges:

                 if dist[u] != float('inf') and dist[u] + w < dist[v]:

                     dist[v] = dist[u] + w

         # Step 3: Check for negative-weight cycles

         for u, v, w in self.edges:

             if dist[u] != float('inf') and dist[u] + w < dist[v]:

                 print("Graph contains negative weight cycle")

                 return None

         # Print the calculated shortest distances

         self.print_solution(dist)

     def print_solution(self, dist):

         print("Vertex Distance from Source")

         for i in range(self.V):

             print(f"{i}\t\t{dist[i]}")

# Example usage

if name == "__main__":

     g = Graph(5)

     g.add_edge(0, 1, -1)

     g.add_edge(0, 2, 4)

     g.add_edge(1, 2, 3)

     g.add_edge(1, 3, 2)

     g.add_edge(1, 4, 2)

     g.add_edge(3, 2, 5)

     g.add_edge(3, 1, 1)

     g.add_edge(4, 3, -3)

     # Source vertex is 0

     g.bellman_ford(0)

Explanation of the Code

1. Graph Initialization: The Graph class initializes with a number of vertices and an empty list of edges. The add_edge method adds an edge to the graph by specifying the source vertex u, destination vertex v, and the edge weight w.

2. Distance Initialization: The bellman_ford method initializes the distances from the source vertex to all other vertices as infinity (float('inf')), except for the source itself, which is set to 0.

3. Relaxation: The algorithm relaxes all the edges |V| - 1 times. If the distance to vertex v through vertex u is shorter than the currently known distance to v, it updates v's distance.

4. Negative Cycle Detection: After |V| - 1 iterations, the algorithm checks for any negative weight cycles. If it finds one, it reports it and stops further processing.

5. Result: The print_solution method displays the shortest distance from the source to all other vertices.

Output for the above code

Running the above code with the example graph should output:

Vertex Distance from Source
0		0
1		-1
2		2
3		-2
4		1

This output shows the shortest distances from the source vertex (0) to all other vertices in the graph.

Advantages and Disadvantages of the Bellman-Ford Algorithm

Advantages:

• Can handle graphs with negative edge weights.

• Detects negative weight cycles.

Disadvantages:

• Slower compared to Dijkstra’s algorithm, with a time complexity of O(V * E), where V is the number of vertices and E is the number of edges.

Conclusion

The Bellman-Ford algorithm is a powerful tool for finding shortest paths in graphs, particularly when dealing with graphs that may contain negative edge weights. While it is less efficient than some other algorithms, its ability to handle more complex graphs makes it invaluable in certain scenarios. By understanding and implementing the Bellman-Ford algorithm in Python, you can solve a variety of shortest path problems in weighted graphs.