Python's Bellman-Ford: Paving the Way to Efficient Solutions.

Shortest paths calculation use case.


In Computer Sciense the Bellman–Ford algorithm is an technique that calculates shortest paths from a source vertex to all of the other vertices in a weighted digraph. Bellman–Ford method is considered slower than Dijkstra's algorithm for the similar task, but it is capable of handling graphs in which some of the edge weights are negative numbers. Handling negative weight edges is very useful for real life tasks like money/finance models, chemistry, physics and many more...

Bellman–Ford algorithm meme.
Bellman–Ford algorithm meme.

Python Knowledge Base: Make coding great again.
- Updated: 2024-07-23 by Andrey BRATUS, Senior Data Analyst.




    Negative weight edges can create negative weight cycles, such cycles that reduce the total path distance by coming back to the same point and such cases should be handed in a correct way.

    Bellman Ford algorithm at the beginning overestimates the length of the path from the starting vertex to all other vertices, then iteratively reduses those estimates by finding new shorter paths.


  1. Bellman–Ford algorithm Python code:



  2. 
    class Graph:
     
        def __init__(self, vertices):
            self.V = vertices
            self.graph = []
     
        # adding edge to graph
        def addEdge(self, u, v, w):
            self.graph.append([u, v, w])
             
        # printing the solution
        def printArr(self, dist):
            print("Vertex Distance from Source")
            for i in range(self.V):
                print("{0}\t\t{1}".format(i, dist[i]))
         
     
        def BellmanFord(self, src):
     
            # Set distances from src to all other vertices as INFINITE
            dist = [float("Inf")] * self.V
            dist[src] = 0
           
            for _ in range(self.V - 1):
                # Update dist value and parent index of the adjacent vertices
                for u, v, w in self.graph:
                    if dist[u] != float("Inf") and dist[u] + w < dist[v]:
                            dist[v] = dist[u] + w
     
            #  check for negative-weight cycles
            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(4)
    g.addEdge(0, 1, 1)
    g.addEdge(0, 2, 3)
    g.addEdge(1, 2, 3)
    g.addEdge(0, 3, -2)
    g.addEdge(1, 3, 2)
    g.addEdge(3, 2, 5)
    g.addEdge(3, -1, 1)
    g.addEdge(3, 3, 1)
     
    # Print the solution
    g.BellmanFord(0)
    
  3. Bellman–Ford algorithm code output:


  4. Bellman–Ford output.



See also related topics: