Алгоритм Беllman-Форда (Bellman-Ford algorithm) — это алгоритм для поиска кратчайших путей в графе, который может обрабатывать отрицательные веса ребер.

class Graph:
    def __init__(self):
        self.edges = []
        self.vertices = set()

    def add_edge(self, u, v, weight):
        self.edges.append((u, v, weight))
        self.vertices.add(u)
        self.vertices.add(v)

    def get_edges(self):
        return self.edges
    
    def get_vertices(self):
        return self.vertices

def bellman_ford(graph, start):
    distances = {v: float('infinity') for v in graph.get_vertices()}
    distances[start] = 0

    for _ in range(len(graph.get_vertices()) - 1):
        for u, v, weight in graph.get_edges():
            if distances[u] + weight < distances[v]:
                distances[v] = distances[u] + weight

    for u, v, weight in graph.get_edges():
        if distances[u] + weight < distances[v]:
            raise ValueError("Graph contains a negative cycle")

    return distances

 # Example usage:
graph = Graph()
graph.add_edge('A', 'B', 1)
graph.add_edge('A', 'C', 4)
graph.add_edge('B', 'C', 2)
graph.add_edge('B', 'D', 5)
graph.add_edge('D', 'E', -3)

for u, v, weight in graph.get_edges():
    print(f"Edge from {u} to {v} with weight {weight}")

start_vertex = 'A'
distances = bellman_ford(graph, start_vertex)
print(distances)  # Output: {'A': 0, 'B': 1, 'C': 3, 'D': -2, 'E': -5}

В этом примере, `graph` — это граф, который представлен в виде словаря, где ключ — имя вершины, значение — список ребер, исходящих из этой вершины. `edges()` — это метод, возвращающий все ребра графа.

Алгоритм Bellman-Форда выполняет |V| — 1 проходов по всем ребрам, где |V| — количество вершин в графе. В каждую из этих проходов, он обновляет расстояние до всех вершин, которые могут быть достигнуты из исходной вершины с помощью ребер, которые были обновлены на предыдущем проходе.

После |V| — 1 проходов, алгоритм может определить, есть ли в графе отрицательный цикл. Если найден отрицательный цикл, то выбрасывается исключение `ValueError`.

В `distances` — это словарь, который хранит расстояния до всех вершин, которые могут быть достигнуты из исходной вершины.