bellman ford Algorithm
The Bellman-Ford algorithm is a graph-based algorithm that solves the single-source shortest path problem, which is used to find the shortest paths from a source vertex to all other vertices in a weighted, directed graph. Developed independently by Richard Bellman and Lester Ford in the late 1950s, the algorithm works by iteratively refining the distance estimates to each vertex and guarantees convergence to the correct solution after a certain number of iterations. The key feature of the Bellman-Ford algorithm is its ability to handle negative weight edges, making it particularly useful in situations where the edge weights can represent costs, time, or other quantities that may have negative values.
The algorithm operates by initializing the distance estimates to all vertices except the source vertex to infinity, and then iteratively updating the distance estimates by relaxing each edge. Relaxation refers to the process of testing whether the current distance estimate to a vertex can be improved by considering an alternative path through an intermediate vertex. The algorithm performs the relaxation step for each edge in the graph, repeating this process for a total of |V|-1 iterations, where |V| represents the number of vertices in the graph. After these iterations, the algorithm guarantees that the distance estimates represent the shortest paths from the source vertex to all other vertices, unless there exists a negative weight cycle in the graph. In such cases, the Bellman-Ford algorithm can detect the negative cycle, thus indicating that no solution exists for the shortest path problem.
from typing import Dict, List
def printDist(dist, V):
print("Vertex Distance")
distances = ("INF" if d == float("inf") else d for d in dist)
print("\t".join(f"{i}\t{d}" for i, d in enumerate(distances)))
def BellmanFord(graph: List[Dict[str, int]], V: int, E: int, src: int) -> int:
"""
Returns shortest paths from a vertex src to all
other vertices.
"""
mdist = [float("inf") for i in range(V)]
mdist[src] = 0.0
for i in range(V - 1):
for j in range(E):
u = graph[j]["src"]
v = graph[j]["dst"]
w = graph[j]["weight"]
if mdist[u] != float("inf") and mdist[u] + w < mdist[v]:
mdist[v] = mdist[u] + w
for j in range(E):
u = graph[j]["src"]
v = graph[j]["dst"]
w = graph[j]["weight"]
if mdist[u] != float("inf") and mdist[u] + w < mdist[v]:
print("Negative cycle found. Solution not possible.")
return
printDist(mdist, V)
return src
if __name__ == "__main__":
V = int(input("Enter number of vertices: ").strip())
E = int(input("Enter number of edges: ").strip())
graph = [dict() for j in range(E)]
for i in range(E):
graph[i][i] = 0.0
for i in range(E):
print("\nEdge ", i + 1)
src = int(input("Enter source:").strip())
dst = int(input("Enter destination:").strip())
weight = float(input("Enter weight:").strip())
graph[i] = {"src": src, "dst": dst, "weight": weight}
gsrc = int(input("\nEnter shortest path source:").strip())
BellmanFord(graph, V, E, gsrc)
