Информатика / Алгоритмы и анализ данных

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

Алгоритм Флойда — Уоршелла находит расстояния между всеми парами вершин, последовательно разрешая новые промежуточные вершины. Его основа — сравнение прямого известного маршрута с маршрутом через очередную вершину.

Опубликовано: 20 октября 2026 г.Обновлено: 20 октября 2026 г.

Формула

d_{ij}^{(k)}=\min\left(d_{ij}^{(k-1)},d_{ik}^{(k-1)}+d_{kj}^{(k-1)}\right)

Схема Флойд: улучшение через B

d(A,C) = min(8, 3 − 1) = 2

Обозначения

$d_{ij}^{(k)}$: лучшая стоимость из i в j с промежуточными вершинами из первых k, единица веса
$i,j$: начало и конец маршрута, идентификатор
$k$: очередная разрешаемая промежуточная вершина, номер
$V$: число вершин, количество

Условия применения

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

Ограничения

Время O(V³) и память O(V²) ограничивают размер сети. Отрицательный цикл нарушает конечность минимума для пар, маршрут которых может пройти через него. Нельзя заменить бесконечность нулём или складывать её как большое конечное число без защиты от переполнения.

Подробное объяснение

Индекс k означает множество разрешённых внутренних вершин, а не число рёбер маршрута. Когда разрешается вершина k, лучший путь из i в j либо обходится без неё, либо проходит через неё. Во втором случае он складывается из лучшего пути i→k и лучшего пути k→j предыдущего этапа.

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

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

После обработки всех промежуточных вершин отрицательная диагональная метка указывает на цикл отрицательного веса. Для пары i,j особенно важно, можно ли из i попасть к такому циклу и затем из него добраться до j: только тогда её стоимость неограничена снизу.

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

Как пользоваться формулой

Постройте матрицу: нули на диагонали, минимальные прямые веса между соседями и бесконечность при отсутствии перехода.
Выберите очередную промежуточную вершину k внешним циклом и переберите все пары i,j, проверяя существование обеих частей пути.
Замените d(i,j) суммой через k, только если она меньше; одновременно обновите таблицу для восстановления маршрутов.
После всех этапов проверьте диагональ и достижимость отрицательных циклов, затем отвечайте на запросы по конечным меткам.

Историческая справка

Роберт Флойд опубликовал Algorithm 97: Shortest path в Communications of the ACM в 1962 году. В том же году Стивен Уоршелл представил работу A theorem on Boolean matrices о булевых матрицах. Современное двойное название связывает близкие схемы последовательного расширения множества допустимых промежуточных вершин. Для расстояний используются минимум и сложение; для достижимости — логические операции. Это различие показывает, почему похожая структура циклов решает разные задачи. Учебная реализация Princeton представляет взвешенный вариант для всех пар и отдельно проверяет отрицательные циклы. Нынешняя запись через матрицу этапов поясняет инвариант динамического программирования и не предполагает, что любая перестановка трёх циклов сохраняет исходный алгоритм.

Историческая линия формулы

Имя Флойда — Уоршелла относится к традиции алгоритмов матричного замыкания. Источники 1962 года различаются задачей: кратчайшие пути у Флойда и булева достижимость у Уоршелла. Здесь применяется взвешенная рекурсия с минимумом и суммой, а не логическая матрица.

Пример

Есть три вершины A,B,C и дуги A→B весом 3, B→C весом −1, A→C весом 8. На диагонали нули, остальные отсутствующие направления имеют ∞. До разрешения B расстояние A→C равно 8. Когда B становится допустимой промежуточной вершиной, сравниваем 8 с 3+(−1) = 2 и заменяем метку на 2. Итоговая матрица по порядку A,B,C имеет строки (0;3;2), (∞;0;−1), (∞;∞;0). Проверка: из C нет исходящих дуг, поэтому обратные маршруты не появились; отрицательная диагональ отсутствует. Кратчайший путь A→C проходит через B и стоит 2 условные единицы. Отрицательное ребро B→C допустимо, поскольку вернуться в B нельзя и отрицательного цикла оно не создаёт.

Частая ошибка

Не ставьте ноль вместо отсутствующего ребра. Не делайте цикл k внутренним при обновлении той же матрицы. Не забывайте ориентированность: d(i,j) не обязано равняться d(j,i). Не трактуйте отрицательное ребро как автоматический отрицательный цикл. Не выдавайте конечный минимум для пары, способной проходить через такой цикл.

Практика

Задачи с решением

Два промежуточных узла

Условие. Есть A→B весом 2, B→C весом 4, C→D весом 1, A→D весом 10. Найдите A→D.

Решение. После допуска B получаем A→C = 2+4 = 6. После допуска C получаем A→D = min(10,6+1) = 7. Маршрут содержит три ребра.

Ответ. 7 через B и C.

Проверка диагонали

Условие. Даны A→B весом 2 и B→A весом −5. Какой цикл обнаружится?

Решение. Обход A→B→A стоит 2−5 = −3. При разрешении B диагональ A уменьшается ниже нуля, что обнаруживает отрицательный цикл.

Ответ. Отрицательный цикл веса −3; конечного минимума для этих пар нет.

Дополнительные источники

https://algs4.cs.princeton.edu/code/javadoc/edu/princeton/cs/algs4/FloydWarshall.html
https://algol60.org/acm/097.pdf
https://projects.csail.mit.edu/jacm/References/warshall1962%3A11.html

Связанные формулы

Информатика

Поиск в ширину: кратчайший путь по числу рёбер

$d(s)=0,\qquad d(v)=d(u)+1\quad\text{при первом открытии }v\text{ из }u$

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

Информатика

Алгоритм Дейкстры: релаксация и кратчайшие расстояния

$d(v)\leftarrow\min\bigl(d(v),d(u)+w(u,v)\bigr),\qquad w(u,v)\geq0$

Алгоритм Дейкстры находит кратчайшие пути от одной вершины при неотрицательных весах рёбер. На каждом шаге окончательно выбирается ещё не выбранная вершина с минимальной текущей меткой.

Информатика

Алгоритм Беллмана — Форда: путь с отрицательными весами

$d_k(v)=\min\left(d_{k-1}(v),\min_{(u,v)\in E}\{d_{k-1}(u)+w(u,v)\}\right)$

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

Информатика

Алгоритм Краскала: вес минимального остовного дерева

$T\in\underset{\text{остовные деревья }S}{\operatorname{arg\,min}}\sum_{e\in S}w(e),\qquad |T|=V-1$

Алгоритм Краскала строит минимальное остовное дерево неориентированного графа: перебирает рёбра по возрастанию веса и принимает только те, которые соединяют разные текущие компоненты.