Флойд — Уоршелл: кратчайшие пути между всеми парами

Таблица для каждой пары

BFS, Дейкстра и Беллман — Форд начинают с одного источника. Флойд — Уоршелл вычисляет ответы для всех упорядоченных пар «откуда — куда». Строка i задаёт начало, столбец j — конец: d[i][j] хранит стоимость, а не число рёбер. У ориентированного ребра обратного перехода может не быть.

Вначале на диагонали стоят нули, для связанных пар — минимальные веса прямых рёбер, для остальных — бесконечность. Ноль означает возможность остаться на месте; отрицательная петля заменяет его своим весом. Бесконечность означает, что путь пока не известен. Одно отрицательное ребро ещё не означает отрицательный цикл.

Проверяем путь через k

Для каждой новой промежуточной вершины k сравниваем d[i][j] с d[i][k] + d[k][j]. Если обе части существуют, а сумма строго меньше прежней стоимости, улучшаем ячейку. Части пути уже могут содержать ранее разрешённые промежуточные вершины. При равенстве оставляем прежний маршрут; минимальное число рёбер среди равных по цене путей не выбирается.

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

Пример читает неизменную матрицу предыдущего этапа и показывает все обновления пар одновременно. Жёлтая строка и столбец дают два слагаемых. Зелёные ячейки улучшились на этом этапе; обводка отмечает выбранную пару. Шаг объявления нового k ещё не применяет обновления. Счётчик проверок учитывает V² пар на применённый этап, включая отсутствующие пути; счётчик улучшений — только строгие уменьшения.

A → D: сначала 10, затем 9 и 3

Прямое ребро A → D стоит 10. Когда B разрешена внутри маршрута, путь A → B → D стоит 3 + 6 = 9. На этом же этапе A → C становится равным 3 + (−2) = 1. Обе ячейки меняются одновременно.

На этапе C уже найденный путь A → C соединяется с C → D: 1 + 2 = 3. Маршрут — A → B → C → D. Итоговые строки: A: [0, 3, 1, 3], B: [∞, 0, −2, 0], C: [∞, ∞, 0, 2], D: [∞, ∞, ∞, 0]. Выберите D → A: пути нет, хотя A → D существует. При единичных весах минимальная стоимость совпала бы с минимальным количеством рёбер.

Как восстановить маршрут

Матрица следующего шага хранит первую вершину после i на текущем пути i → j. Для прямого ребра next[i][j]=j. При улучшении через k копируем первый шаг из прежнего пути i → k. Последовательно переходя по этим указателям, восстанавливаем конечный маршрут. Путь из вершины в неё же состоит из одной вершины и стоит ноль, если на эту пару не влияет отрицательный цикл.

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

Для каких пар нет конечного минимума

После всех V этапов отрицательная диагональ d[k][k] указывает на отрицательный замкнутый маршрут. Пара i → j получает −∞ тогда и только тогда, когда для некоторой такой k можно пройти из i в k и из k в j. Повторяя цикл, можно снижать цену сколько угодно. Конечного кратчайшего маршрута для этих пар нет. Отрицательный цикл в отдельной компоненте не отменяет конечные ответы в других частях графа.

В примере с циклом добавлено ребро C → B веса 1: B → C → B стоит −1. Для A → D конечного минимума нет, D → A остаётся недостижимой, а D → D стоит ноль. В примере с отдельным циклом у изолированной E есть отрицательная петля; A → D по-прежнему стоит 3. Пока обрабатывается отрицательный цикл, конечные числа в таблице — промежуточные стоимости маршрутов, а не ответы о кратчайших путях; зацикленную цепочку следующих вершин не рисуем.

Время, память и границы применения

Алгоритм требует Θ(V³) времени и Θ(V²) рабочей памяти, включая следующие шаги и два слоя матрицы. Классическая реализация с обновлением на месте тоже использует Θ(V²) памяти; здесь слои разделены, чтобы визуальный этап не зависел от порядка просмотра пар. Классификация пар через отрицательные циклы добавляет O(V³) времени и O(V²) памяти достижимости, сохраняя общие оценки.

Плеер хранит O(V) независимых кадров по O(V²) значений: история занимает O(V³) памяти сверх рабочей памяти алгоритма. Интерактивный ввод ограничен шестью вершинами, уникальными направленными парами и целыми весами от −99 до 99. Функция из статьи допускает параллельные рёбра и берёт самое лёгкое, проверяет целые веса и отклоняет небезопасные суммы. Для дробных весов нужна отдельная политика ошибок вычислений.

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

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

Функция повторяет переходы между фиксированными слоями из примера и возвращает расстояния, следующие шаги, вершины с отрицательной диагональю и запрос маршрута. Infinity означает недостижимость, −Infinity — отсутствие конечного минимума. Проверки не дают незаметно выйти за пределы безопасных целых JavaScript.

function floydWarshall(n, edges) {
    if (!Number.isInteger(n) || n < 1) throw Error("Invalid vertex count");
    const valid = v => Number.isInteger(v) && v >= 0 && v < n;
    let d = Array.from({length: n}, (_, i) =>
        Array.from({length: n}, (_, j) => i === j ? 0 : Infinity));
    let next = Array.from({length: n}, (_, i) =>
        Array.from({length: n}, (_, j) => i === j ? i : null));
    for (const {from, to, weight} of edges) {
        if (!valid(from) || !valid(to) || !Number.isSafeInteger(weight))
            throw Error("Invalid edge");
        if (weight < d[from][to]) {
            d[from][to] = weight; next[from][to] = to;
        }
    }
    for (let k = 0; k < n; k++) {
        const before = d, oldNext = next;
        d = before.map(row => [...row]);
        next = oldNext.map(row => [...row]);
        for (let i = 0; i < n; i++) for (let j = 0; j < n; j++) {
            if (!Number.isFinite(before[i][k]) || !Number.isFinite(before[k][j]))
                continue;
            const candidate = before[i][k] + before[k][j];
            if (!Number.isSafeInteger(candidate)) throw Error("Cost overflow");
            if (candidate < before[i][j]) {
                d[i][j] = candidate; next[i][j] = oldNext[i][k];
            }
        }
    }
    const negative = d.flatMap((row, k) => row[k] < 0 ? [k] : []);
    const reachable = d.map(row => row.map(Number.isFinite));
    for (let i = 0; i < n; i++) for (let j = 0; j < n; j++)
        if (negative.some(k => reachable[i][k] && reachable[k][j])) {
            d[i][j] = -Infinity; next[i][j] = null;
        }
    function path(from, to) {
        if (!valid(from) || !valid(to)) throw Error("Invalid pair");
        if (!Number.isFinite(d[from][to])) return [];
        const route = [from];
        while (from !== to) {
            const hop = next[from][to];
            if (hop === null || route.includes(hop) || route.length >= n)
                throw Error("Invalid next-hop chain");
            route.push(hop); from = hop;
        }
        return route;
    }
    return {distance: d, next, negative, path};
}

// A=0, B=1, C=2, D=3
const result = floydWarshall(4, [
    {from: 0, to: 1, weight: 3}, {from: 1, to: 2, weight: -2},
    {from: 2, to: 3, weight: 2}, {from: 0, to: 3, weight: 10},
    {from: 1, to: 3, weight: 6}
]);
console.log(result.distance[0][3]); // 3
console.log(result.path(0, 3));     // [0, 1, 2, 3]