bellman_ford.py

def bellman_ford(graph, source):
    # Initialize distances and predecessors
    distances = {vertex: float('infinity') for vertex in graph}
    predecessors = {vertex: None for vertex in graph}
    distances[source] = 0

    # Relax edges repeatedly
    for _ in range(len(graph) - 1):
        for vertex in graph:
            for neighbor in graph[vertex]:
                if distances[vertex] + graph[vertex][neighbor] < distances[neighbor]:
                    distances[neighbor] = distances[vertex] + graph[vertex][neighbor]
                    predecessors[neighbor] = vertex

    # Check for negative-weight cycles
    for vertex in graph:
        for neighbor in graph[vertex]:
            if distances[vertex] + graph[vertex][neighbor] < distances[neighbor]:
                raise Exception("Negative-weight cycle detected")

    return distances, predecessors

# Test data
graph = {
    'A': {'B': -1, 'C': 4},
    'B': {'C': 3, 'D': 2, 'E': 2},
    'C': {},
    'D': {'B': 1, 'C': 5},
    'E': {'D': -3}
}

source = 'A'

# Run the algorithm
distances, predecessors = bellman_ford(graph, source)

# Expected output
print("Distances:", distances)
print("Predecessors:", predecessors)

# Result:
# Distances: {'A': 0, 'B': -1, 'C': 2, 'D': -2, 'E': 1}
# Predecessors: {'A': None, 'B': 'A', 'C': 'B', 'D': 'E', 'E': 'B'}