Алгоритм Флойда — Уоршелла

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

Небольшой граф с длинами на ребрах рядом с таблицей расстояний между каждой парой вершин, в которой выделены одна строка и один столбец
Небольшой граф с длинами на ребрах рядом с таблицей расстояний между каждой парой вершин, в которой выделены одна строка и один столбец

Идея

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

Шаг за шагом

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

Пример

Возьмем четыре вершины и ребра A–B длиной 3, B–C 1, A–C 5 и C–D 2. Таблица начинается с них и с бесконечности для A–D и B–D. Раунд A ничего не меняет: любой путь через A длиннее. Раунд B находит путь из A в C через B: 3 + 1 = 4, меньше, чем 5. Раунд C находит путь из A в D через C: 4 + 2 = 6 и из B в D: 1 + 2 = 3 — оба первые найденные. Раунд D ничего не меняет. Итоговая таблица: A–B 3, A–C 4, A–D 6, B–C 1, B–D 3, C–D 2.

Почему важен порядок циклов

Промежуточная вершина k должна быть во внешнем цикле. После раунда для k каждая клетка — это кратчайшее расстояние, в котором промежуточными могут быть только первые k вершин, и следующий раунд опирается на это: лучший путь через новую промежуточную вершину — это лучший путь до нее плюс лучший путь от нее, и оба уже верны. Если поместить k во внутренний цикл, эта гарантия пропадает и могут остаться неверные расстояния. Обновлять таблицу на месте во время раунда безопасно, потому что строка и столбец самой k в этом раунде не меняются.

История и применения

Бернар Руа описал этот метод в 1959 году. В 1962 году Стивен Уоршелл опубликовал его для транзитивного замыкания, где спрашивается лишь, может ли одна вершина достичь другой, а Роберт Флойд — для кратчайших путей. Метод вычисляет таблицы расстояний и таблицы маршрутизации, находит диаметр сети, показывает, какие вершины достижимы из каких, а отрицательная клетка на диагонали выдает отрицательный цикл.

Попробуйте сами

Откройте приложение и нажмите Шаг. Граф находится с одной стороны, таблица — с другой. Каждый раунд выделяет строку и столбец текущей промежуточной вершины; каждый шаг записывает более короткое расстояние для одной пары и обводит две клетки, которые были сложены. Клетки, измененные в этом раунде, подсвечены. Выберите старт и цель, чтобы увидеть кратчайший путь между ними, когда таблица будет готова.

Часто задаваемые вопросы

Какова временная сложность алгоритма Флойда — Уоршелла?

O(n³) для n вершин независимо от числа ребер и O(n²) памяти для таблицы. Это лучший выбор для небольших или плотных графов, где его простой цикл работает очень быстро.

Флойд — Уоршелл или Дейкстра из каждой вершины?

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

Алгоритм Флойда — Уоршелла — это динамическое программирование?

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

Что такое транзитивное замыкание?

Это таблица того, какие вершины достижимы из каких, без учета расстояний. Вариант алгоритма Уоршелла вычисляет ее с помощью "или" и "и" вместо "min" и "+".

Готовы попробовать?

Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.

Попробовать алгоритм Флойда — Уоршелла