Алгоритм Флойда — Уоршелла
В старых дорожных атласах в конце была таблица: расстояние между каждой парой городов. Алгоритм Флойда — Уоршелла — способ вычислить такую таблицу, и это один из самых коротких алгоритмов, когда-либо написанных: три цикла, одно сравнение — и каждое кратчайшее расстояние встает на свое место.
Идея
Алгоритм Дейкстры и алгоритм Беллмана — Форда находят кратчайшие расстояния от одного старта. Алгоритм Флойда — Уоршелла находит их сразу от каждой вершины до каждой другой, в таблице со строкой и столбцом на каждую вершину. Он начинает с того, что ребра говорят напрямую, а затем улучшает всю таблицу, разрешая все больше вершин как промежуточные на пути.
Шаг за шагом
Заполните таблицу: 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 в своем браузере — установка не требуется, для запуска не требуется кредитная карта.
Попробовать алгоритм Флойда — Уоршелла