Bellman–Ford algorithm.

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.



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.


Bellman–Ford algorithm Python code:




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)
Bellman–Ford output.



See also related topics: