Алгоритм Беллмана-Форда

Алгоритм Беллмана-Форда находит кратчайшие пути от одной вершины во взвешенном графе и, в отличие от Дейкстры, допускает отрицательные рёбра. Он V−1 раз релаксирует все рёбра; дополнительный проход выявляет отрицательные циклы.

Сложность: время O(V · E); память: O(V). Медленнее Дейкстры, но универсальнее.

def bellman_ford(edges, n, start):
    dist = [float("inf")] * n
    dist[start] = 0
    for _ in range(n - 1):
        for u, v, w in edges:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    return dist