← Назад к графовым алгоритмам

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

Поиск кратчайших путей от одной вершины (работает с отрицательными весами)

🐍 Python
n, m = map(int, input().split())
INF = 10**9
G = []

for _ in range(m):
    a, b, w = map(int, input().split())
    a -= 1
    b -= 1
    G.append([a, b, w])

F = [INF] * n
F[0] = 0

for k in range(1, n):
    for g in G:
        a = g[0]
        b = g[1]
        w = g[2]
        if F[a] + w < F[b]:
            F[b] = F[a] + w

print(*F)
⚙️ C++
#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9;

int main() {
    int n, m;
    cin >> n >> m;
    
    vector<tuple<int, int, int>> G;
    
    for (int i = 0; i < m; i++) {
        int a, b, w;
        cin >> a >> b >> w;
        a--; b--;
        G.push_back({a, b, w});
    }
    
    vector<int> F(n, INF);
    F[0] = 0;
    
    for (int k = 1; k < n; k++) {
        for (auto [a, b, w] : G) {
            if (F[a] + w < F[b]) {
                F[b] = F[a] + w;
            }
        }
    }
    
    for (int i = 0; i < n; i++) {
        cout << F[i] << " ";
    }
    cout << endl;
    
    return 0;
}

Как работает алгоритм Форда-Беллмана?

Алгоритм Форда-Беллмана находит кратчайшие пути от одной вершины до всех остальных. Его главное преимущество — возможность работать с рёбрами, имеющими отрицательный вес (в отличие от алгоритма Дейкстры).

Основная идея алгоритма — релаксация рёбер. Алгоритм повторяет процесс релаксации всех рёбер n-1 раз, где n — количество вершин. Этого достаточно, чтобы найти кратчайшие пути в графе без отрицательных циклов.

Шаги алгоритма:

Почему n-1 проход? Кратчайший путь в графе без отрицательных циклов может содержать не более n-1 ребра. После каждого прохода мы "распространяем" кратчайшие пути на одну вершину дальше.

Временная сложность: O(n × m), где n — количество вершин, m — количество рёбер.

Пространственная сложность: O(n + m).

Формат ввода и вывода

Ввод:

Вывод:

Пример ввода:

4 5
1 2 5
1 3 3
2 3 2
2 4 7
3 4 4

Здесь:
n=4, m=5
Стартовая вершина: 1

Вывод: 0 5 3 7
(расстояния до вершин 1,2,3,4)

Пример с отрицательными весами:

3 3
1 2 4
2 3 -3
1 3 2

Вывод: 0 4 1
(путь 1→2→3 короче, чем прямое ребро 1→3: 4 + (-3) = 1)

Попробовать алгоритм Форда-Беллмана онлайн

Введите граф в формате, описанном выше:

Результат появится здесь...