Беллман — Форд: отрицательные веса и циклы

Зачем ещё один проход

Рёбра здесь ориентированные: стрелка разрешает движение только в одну сторону. Вес может обозначать суммарную стоимость с возвратом или скидкой, поэтому допускается отрицательное число. Это не лабиринт, где по каждому проходу автоматически можно вернуться назад. В неориентированном графе доступное отрицательное ребро при движении туда и обратно уже даёт отрицательный замкнутый маршрут.

Дейкстра окончательно фиксирует минимальную предварительную оценку, опираясь на неотрицательные веса. Отрицательное ребро нарушает эту гарантию. Беллман — Форд так вершины не закрывает: он несколько раз просматривает весь список рёбер и улучшает оценки. В отличие от Дейкстры с одной целью здесь нельзя останавливаться при первом достижении или улучшении цели.

Одно ребро — одна попытка улучшения

В начале d(старт)=0, остальные оценки равны бесконечности. Для ребра u → v с весом w пробуем d(u)+w. Если u уже достижима и сумма строго меньше d(v), обновляем d(v) и ребро предка. Это релаксация. При равенстве прежний предок остаётся; недостижимое начало пропускаем, ничего не прибавляя к бесконечности.

Рёбра проверяются в порядке входного списка, расстояния обновляются на месте. Поэтому новое значение может сразу попасть в следующее ребро этого же прохода. Проход не является одновременной волной, а его номер не задаёт точное число рёбер в показанных маршрутах. Другой порядок рёбер может изменить промежуточные состояния, число проходов и выбор среди равноценных путей.

От стоимости четыре к стоимости три

Исходный порядок: A → G (2), B → A (−4), S → A (2), S → B (5). В первом проходе первые два ребра пропускаются: их начала ещё недостижимы. Затем получаем d(A)=2 и d(B)=5. У G пока бесконечность.

Во втором проходе сначала получаем d(G)=4 через A. Позже ребро B → A улучшает d(A) с 2 до 5−4=1. Ребро A → G в этом проходе уже проверено, поэтому новая оценка доходит до G в третьем: d(G)=1+2=3. Итоговый путь S → B → A → G стоит 5−4+2=3. В нём больше рёбер, чем в S → A → G со стоимостью четыре.

Почему хватает V−1 основных проходов

Если достижимого отрицательного цикла нет, кратчайший маршрут можно выбрать без повторения вершин, то есть не длиннее V−1 рёбер. После прохода k окончательны расстояния до вершин, чей кратчайший путь содержит не больше k рёбер. Обновления на месте могут передать улучшение и дальше за тот же проход. Поэтому V−1 основных проходов достаточно для конечных расстояний до достижимых вершин.

Если полный проход ничего не изменил, для каждого достижимого ребра уже выполнено d(v) ≤ d(u)+w. Новый такой же просмотр ничего не улучшит, и эта реализация останавливается досрочно. Посреди прохода она не останавливается. При V=1 основных проходов нет, но контрольная проверка всё равно выполняется и обнаруживает отрицательную петлю.

Отрицательный цикл и вершины после него

После V−1 проходов с улучшениями ещё раз проверяем все рёбра, сохраняя оценки неизменными. Возможное строгое улучшение из достижимой вершины доказывает наличие отрицательного цикла, достижимого от старта. Отдельный недостижимый цикл не срабатывает: у его вершин по-прежнему бесконечность.

Плеер дополнительно определяет последствия для каждой вершины. Отмечаем концы всё ещё улучшаемых рёбер, затем все вершины, достижимые из них. Их расстояния равны −∞: можно несколько раз пройти отрицательный цикл, произвольно уменьшить стоимость и лишь затем пойти к вершине. Красная область — затронутые вершины, а не восстановленный список рёбер самого цикла.

Цель может быть недостижимой (∞), иметь конечный минимум или быть достижимой без конечного минимума (−∞). Цикл влияет на цель, только если он достижим от старта и из него можно попасть в цель. Попробуйте боковой цикл: он достижим, но стоимость G остаётся равной четырём. Цикл в отдельной компоненте не меняет исходный конечный маршрут. Для недостижимой цели и цели без конечного минимума путь не восстанавливается.

Как читать и менять пример

Жёлтым выделено проверяемое ребро; предложение над графом показывает старое расстояние до начала, новую сумму и предыдущую оценку конца. Завершённый основной проход увеличивает счётчик. Контроль цикла подписан отдельно. Зелёным показан сохранённый путь. Красные вершины достижимы из обнаруженного отрицательного цикла.

«Просмотров рёбер» считает каждое ребро в основных проходах и контроле, включая недостижимые начала. «Улучшений» — строгие уменьшения в основных проходах, в том числе замену бесконечности числом. Распространение отметок и восстановление пути — отдельные этапы, они не увеличивают эти два счётчика. Во время незавершённых проходов конечные числа — ещё оценки, а не обещанные минимальные стоимости.

Выберите пример, старт и цель или измените вес ребра. Ошибка ввода сохраняет текущий корректный поиск. Демо принимает 1–8 вершин с уникальными подписями, до 32 ориентированных рёбер без повторения упорядоченных пар и целые веса от −99 до 99. Петли и нулевые веса допустимы. Можно остановить поиск, шагать в обе стороны, перематывать, поделиться состоянием на паузе, развернуть плеер и сохранить немую анимацию всего поиска.

Память алгоритма и история плеера

Основные проходы и контроль занимают O(VE+V) времени с учётом начальной инициализации; для графов с рёбрами обычно пишут O(VE). Дополнительная разметка просматривает список рёбер для каждой вершины очереди и добавляет O(VE). Рабочие массивы, множество начальных отметок и очередь занимают O(V) памяти без входного графа. С индексом смежности разметку можно сделать за O(V+E), потратив дополнительную память.

Визуализация сохраняет одну неизменяемую копию графа размером O(V+E) и O(V) данных на событие. Событий O(VE+V), поэтому верхняя оценка истории — O(V²(E+1)) дополнительно к графу. Это стоимость интерфейса воспроизведения, отдельная от рабочей памяти Беллмана — Форда. Темп анимации не измеряет быстродействие программы.

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

Ниже функция вычисляет ответ без истории визуализации. edges — упорядоченные объекты {from,to,weight}, номера вершин — от 0 до n−1. Порядок обновлений на месте, строгие сравнения, досрочная остановка и классификация затронутых вершин совпадают с демо. Веса и промежуточные стоимости должны быть безопасными целыми JavaScript; переполнение отклоняется. Более строгие ограничения демо нужны для читаемых подписей и объёма истории.

function bellmanFord(n, edges, start, target) {
    const valid = v => Number.isInteger(v) && v >= 0 && v < n;
    if (!Number.isInteger(n) || n < 1 || !valid(start) || !valid(target))
        throw Error("Invalid vertices");
    for (const e of edges)
        if (!valid(e.from) || !valid(e.to) || !Number.isSafeInteger(e.weight))
            throw Error("Expected integer edge weights");
    const d = Array(n).fill(Infinity), parent = Array(n).fill(null);
    const affected = Array(n).fill(false);
    d[start] = 0;
    let fixed = false;
    for (let pass = 1; pass < n; pass++) {
        let changed = false;
        for (let id = 0; id < edges.length; id++) {
            const {from, to, weight} = edges[id];
            if (d[from] === Infinity) continue;
            const candidate = d[from] + weight;
            if (!Number.isSafeInteger(candidate)) throw Error("Cost overflow");
            if (candidate < d[to]) {
                d[to] = candidate; parent[to] = id; changed = true;
            }
        }
        if (!changed) { fixed = true; break; }
    }
    const queue = [];
    if (!fixed) for (const {from, to, weight} of edges) {
        if (d[from] === Infinity) continue;
        const candidate = d[from] + weight;
        if (!Number.isSafeInteger(candidate)) throw Error("Cost overflow");
        if (candidate < d[to] && !affected[to]) {
            affected[to] = true; queue.push(to);
        }
    }
    const negativeCycle = queue.length > 0;
    for (let head = 0; head < queue.length; head++)
        for (const {from, to} of edges)
            if (from === queue[head] && !affected[to]) {
                affected[to] = true; queue.push(to);
            }
    for (let v = 0; v < n; v++) if (affected[v]) {
        d[v] = -Infinity; parent[v] = null;
    }
    const result = affected[target] ? "unbounded"
        : d[target] === Infinity ? "unreachable" : "finite";
    const path = [];
    if (result === "finite") {
        let v = target;
        for (let count = 0; ; count++) {
            if (count >= n) throw Error("Invalid parent chain");
            path.push(v);
            if (v === start) break;
            v = edges[parent[v]].from;
        }
        path.reverse();
    }
    return {distance: d, parentEdge: parent, affected, negativeCycle, result, path};
}