Обратите внимание на другие наши ресурсы: Youtube | Telegram | VK | Rutube | Dzen | Boosty

Определение

Алгоритм Беллмана — Форда - алгоритм на графах, который находит кратчайшие пути от одной из вершин графа до всех остальных. В отличие от алгоритма Дейкстры, алгоритм Беллмана-Форда допускает ребра с отрицательным весом.

---

Принцип работы алгоритма

Дан взвешенный ориентированный граф $G(V, E)$, в котором возможны отрицательные рёбра. Необходимо от вершины $A$ до всех остальных вершин найти пути минимальной стоимости.

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

Начальные значения на графе:

Суть алгоритма:

1. Проход по всем рёбрам $(V-1)$ раз по рекуррентной формуле $dist_Y = минимум\;из\;dist_Y\;и\;(dist_X + graph_{[X][Y]})$, где $dist_Y$ - текущее расстояние от A до Y, $graph_{[X][Y]}$ - вес ребра из X в Y
2. Проход по всем рёбрам для проверки графа на отрицательный цикл: если $dist_Y > dist_X + graph_{[X][Y]}$, то оптимальных путей в графе не существует

Отрицательным называется цикл в графе, сумма рёбер которого отрицательна:

Пример прохода по всем рёбрам в графе:

1. Рассмотрим вершину B. Пройдя в эту вершину, изменится длина пути A-B-F с бесконечности до -1. Длина пути A-B-C (6) больше чем длина пути A-C (4), поэтому длина пути в вершину C не изменяется

2. Рассмотрим вершину C. Пройдя в эту вершину изменится длина пути в вершину F, ведь длина пути A-C-F (-3), что меньше длины пути A-B-F (-1). Длина пути в вершину D изменится, потому что длина пути A-C-D(2) меньше длины пути A-D(5), длина пути в вершину E изменится с бесконечности до длины пути A-C-E (7).

3. Рассмотрим вершину D. Длина пути в вершину E изменится, потому что длина пути A-C-D-E(6) короче длины пути A-C-E(7)

4. Рассмотрим вершину E. Длина пути в вершину G изменится с бесконечности до 6, длина пути в вершину F не изменится, потому что длина пути A-C-D-E-F(12) больше длины пути A-C-F(-3)

5. Рассмотрим вершину F. Длина пути в вершину G изменится, так как длина пути A-C-F-G(-13) меньше длины пути A-C-D-E-G(6)

6. Рассмотрим вершину G. Из неё нет доступных путей.

7. В результате действия алгоритма получим следующий граф:

---

Вычислительная сложность

Инициализация занимает $O(V)$ времени, каждый из $|V|−1$ проходов требует $O(E)$ времени, обход по всем ребрам для проверки наличия отрицательного цикла занимает $O(E)$ времени. Значит алгоритм Беллмана-Форда работает за $O(V*E)$ времени.

---

Псевдокод

V - количество вершин
graph - список смежности, в котором гранится граф
dist - массив оптимальных значений
visited - массив булевых значений, в котором помечаются все посещённые вершины
start - вершина, до которой необходимо посчитать кратчайшие пути до всех остальных
is_updated - булево значение, которое на каждом проходе по всем рёбрам проверяет наличие изменений

функция беллман_форд_минимум(graph):
    заполнение массива dist размерности V бесконечностями
    dist[start] <- 0

    для k от 0 до (v - 1):
        is_updated <- "Ложь"
    
        для каждого i в graph:
            для каждых j, w в graph[i]:
                если (dist[i] + w) < dist[j], то
                    dist[j] <- (dist[i] + w)
                    is_updated <- "Правда"
        если не is_updated, то
            выход из цикла

    для каждого i в графе:
        для каждых j, w в graph[i]:
            если dist[j] > (dist[i] + w), то
                вернуть "Ложь", dist

    вернуть "Правда", dist

---

Реализация на Python

Аннотация:
bellman_ford_minimum - алгоритм Беллмана-Форда
graph - матрица смежности, в которой хранится граф
amount - количество вершин
start - вершина, от которой необходимо посчитать кратчайшие пути до всех остальных
dist - массив оптимальных значений
was_updated - булево значение, которое на каждом проходе по всем рёбрам проверяет наличие изменений в dist

def bellman_ford_minimum(graph, amount, start):
    dist = [inf] * amount
    dist[start] = 0

    for _ in range(amount - 1):
        was_updated = False
        for i in graph:
            for j, w in graph[i]:
                if dist[i] + w > dist[j]:
                    dist[j] = dist[i] + w
                    was_updated = True
        if not was_updated:
            break

    for i in graph:
        for j, w in graph[i]:
            if dist[j] < dist[i] + w:
                return False, dist

    return True, dist

---

Олимпиадная реализация на С++

Аннотация:
bellman_ford_min - алгоритм Беллмана-Форда 
graph - матрица смежности, в которой хранится граф
v - количество вершин
start - вершина, от которой необходимо посчитать кратчайшие пути до всех остальных
dist - массив оптимальных значений
is_updated - булево значение, которое на каждом проходе по всем рёбрам проверяет наличие изменений

pair<int, vector<int>> bellman_ford_min(const unordered_map<int, vector<std::pair<int, int>>> &graph, int v, int start) {
    vector<int> dist(v, numeric_limits<int>::max());
    dist[start] = 0;
    for (int t = 0; t < v - 1; ++v) {
        bool is_updated = false;
        for (auto &x : graph) {
            auto &i = x.first;
            for (auto &y : x.second) {
                auto &j = y.first;
                auto &w = y.second;
                if (dist[i] + w < dist[j]) {
                    dist[j] = dist[i] + w;
                    is_updated = true;
                }
            }
        }
        if (not is_updated)
            break;
    }
    for (auto &x : graph) {
        auto &i = x.first;
        for (auto &y : x.second) {
            auto &j = y.first;
            auto &w = y.second;
            if (dist[j] > dist[i] + w)
                return {false, dist};
        }
    }
    return {true, dist};
}

---

Продуктовая реализация на С++

Аннотация:
template - шаблон функции
typename ValueType - шаблонный тип данных параметра
bellman_ford_minimum - алгоритм Беллмана-Форда
graph - матрица смежности, в которой хранится граф
amount - количество вершин
start - вершина, от которой необходимо посчитать кратчайшие пути до всех остальных
distances - массив оптимальных значений
is_updated - булево значение, которое на каждом проходе по всем рёбрам проверяет наличие изменений

template<typename ValueType>
std::pair<bool, std::vector<ValueType>> bellman_ford_minimum(
        const std::unordered_map<ValueType, std::vector<std::pair<ValueType, ValueType>>> &graph,
        ValueType amount, ValueType start) {
    std::vector<ValueType> distances(v, std::numeric_limits<ValueType>::max());
    distances[start] = 0;

    for (int t = 0; t < v - 1; ++v) {
        bool is_updated = false;

        for (auto &x : graph) {
            auto &i = x.first;
            for (auto &y : x.second) {
                auto &j = y.first;
                auto &w = y.second;
                if (distances[i] + w < distances[j]) {
                    distances[j] = distances[i] + w;
                    is_updated = true;
                }
            }
        }

        if (not is_updated)
            break;
    }

    for (auto &x : graph) {
        auto &i = x.first;
        for (auto &y : x.second) {
            auto &j = y.first;
            auto &w = y.second;

            if (distances[j] > distances[i] + w)
                return {false, distances};
        }
    }

    return {true, distances};
}