def bellman_ford(graph, source):
# Step 1: Initialize distances
distances = {vertex: float('inf') for vertex in graph}
distances[source] = 0
# Step 2: Relax edges |V| - 1 times
for _ in range(len(graph) - 1):
for u in graph:
for v, weight in graph[u].items():
if distances[u] != float('inf') and distances[u] + weight < distances[v]:
distances[v] = distances[u] + weight
print(distances)
# Step 3: Check for negative weight cycles
for u in graph:
for v, weight in graph[u].items():
if distances[u] != float('inf') and distances[u] + weight < distances[v]:
raise ValueError("Graph contains negative weight cycle")
return distances
# Example
graph = {
'A': { 'F': 4, 'G': 10},
'B': {'A': -5, 'D': 4},
'C': {'D': 2},
'D': {'E': 1},
'E': {'B': 2},
'F': {'E': 5},
'G': {'C': -9, 'E': -8, 'F': -4},
'H': {'A': 7, 'G': 8},
}
source = 'H'
shortest_distances = bellman_ford(graph, source)
print(shortest_distances)