Флойд-Уоршелл
Все кратчайшие пути сразу: пробуем каждую вершину как пересадку и обновляем таблицу.
1function floydWarshall(w: number[][]): number[][] {2 const n = w.length3 const d = w.map((row) => row.slice())4 5 for (let k = 0; k < n; k++) {6 for (let i = 0; i < n; i++) {7 for (let j = 0; j < n; j++) {8 if (d[i][k] + d[k][j] < d[i][j]) {9 d[i][j] = d[i][k] + d[k][j]10 }11 }12 }13 }14 15 return d16}Проблема
Из любой вершины в любую нужно знать кратчайший путь — и не для одной пары, а для всех сразу. Дейкстра решает «из одной точки», Беллман-Форд — то же с отрицательными рёбрами. Флойд-Уоршелл отвечает на ВСЕ вопросы одним прогоном матрицы.
Что вы видите
Таблица-матрица: строка — откуда, столбец — куда, в клетке — текущая цена пути. Подсвеченная строка и столбец — вершина-пересадка k: для каждой клетки спрашиваем «не дешевле ли через k?». Два подсвеченных числа складываются; если сумма меньше — клетка вспыхивает и обновляется.
Как это работает
Динамическое программирование по пересадкам. На шаге k в таблице уже лежат кратчайшие пути с пересадками только в вершинах 1..k−1. Пробуя пересадку k, сравниваем d[i][j] с d[i][k] + d[k][j] — путь через k складывается из двух уже проверенных половинок. После n шагов таблица содержит кратчайшие пути без ограничений. O(n³), зато сразу всё — и отрицательные рёбра допустимы (без отрицательных циклов).
Пошаговый разбор
- 01
Прямые дороги
В таблице только веса рёбер; ∞ — прямого пути нет.
- 02
Пересадка k
Подсвечены строка и столбец k: все пути, которые могут идти через k.
- 03
Сравнение
d[i][k] + d[k][j] против d[i][j]: через пересадку дешевле?
- 04
Обновление
Да — клетка вспыхивает и запоминает новую цену.
- 05
Все пары
После n пересадок таблица = все кратчайшие пути.
Complexity и ограничения
O(n³) времени, O(n²) памяти — на n до ~500. Отрицательные рёбра допустимы; отрицательный цикл сделает диагональ отрицательной (детектор).
Edge cases
- Отрицательный цикл
d[i][i] < 0 после всех шагов — цикл найден, кратчайших путей нет.
- Полный граф
Пересадки ничего не улучшают — таблица не меняется.
- n = 2
Одна возможная пересадка — таблица почти не меняется.
Где встречается в реальности
Транзитные маршруты
Все пары аэропортов с пересадками — таблица цен для всего хаба.
Графы в биоинформатике
Расстояния между всеми парами белков/узлов сетей.
Транзитивное замыкание
Тот же цикл с boolean-матрицей: «достижим ли j из i».
Связанные алгоритмы
«Одна таблица — и ВСЕ кратчайшие пути сразу»
Тот же сценарий StepSequence в вертикальной композиции — с safe zones и записью WebM ниже на странице.
Shorts 9:16
Вертикальная композиция строится той же последовательностью шагов, что и страница: safe zones отмечены пунктиром (там живёт UI платформ), биты сценария подсвечиваются по прогрессу. Кнопка записи сохраняет WebM — детерминированная StepSequence даёт воспроизводимый ролик без монтажа.