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...
Python Knowledge Base: Make coding great again.
- Updated:
2024-07-26 by Andrey BRATUS, Senior Data Analyst.
Bellman–Ford algorithm Python code:
Bellman–Ford algorithm code output:
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.
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)
