bellman_ford.py

from __future__ importannotations


defprint_distance(distance: list[float], src):
print(f"Vertex\tShortest Distance from vertex {src}")
fori, dinenumerate(distance):
print(f"{i}\t\t{d}")


defcheck_negative_cycle(
graph: list[dict[str, int]], distance: list[float], edge_count: int
):
forjinrange(edge_count):
u, v, w= (graph[j][k] forkin ["src", "dst", "weight"])
ifdistance[u] !=float("inf") anddistance[u] +w<distance[v]:
returnTrue
returnFalse


defbellman_ford(
graph: list[dict[str, int]], vertex_count: int, edge_count: int, src: int
) ->list[float]:
"""
 Returns shortest paths from a vertex src to all
 other vertices.
 >>> edges = [(2, 1, -10), (3, 2, 3), (0, 3, 5), (0, 1, 4)]
 >>> g = [{"src": s, "dst": d, "weight": w} for s, d, w in edges]
 >>> bellman_ford(g, 4, 4, 0)
 [0.0, -2.0, 8.0, 5.0]
 >>> g = [{"src": s, "dst": d, "weight": w} for s, d, w in edges + [(1, 3, 5)]]
 >>> bellman_ford(g, 4, 5, 0)
 Traceback (most recent call last):
 ...
 Exception: Negative cycle found
 """
distance= [float("inf")] *vertex_count
distance[src] =0.0

for_inrange(vertex_count-1):
forjinrange(edge_count):
u, v, w= (graph[j][k] forkin ["src", "dst", "weight"])

ifdistance[u] !=float("inf") anddistance[u] +w<distance[v]:
distance[v] =distance[u] +w

negative_cycle_exists=check_negative_cycle(graph, distance, edge_count)
ifnegative_cycle_exists:
raiseException("Negative cycle found")

returndistance


if__name__=="__main__":
importdoctest

doctest.testmod()

V=int(input("Enter number of vertices: ").strip())
E=int(input("Enter number of edges: ").strip())

graph: list[dict[str, int]] = [{} for_inrange(E)]

foriinrange(E):
print("Edge ", i+1)
src, dest, weight= (
int(x)
forxininput("Enter source, destination, weight: ").strip().split(" ")
 )
graph[i] = {"src": src, "dst": dest, "weight": weight}

source=int(input("\nEnter shortest path source:").strip())
shortest_distance=bellman_ford(graph, V, E, source)
print_distance(shortest_distance, 0)