- Текущая промежуточная
- Уже была промежуточной
- Сокращенная пара
- Путь
Алгоритм Флойда — Уоршелла
Как далеко от каждого города до любого другого? Алгоритм Флойда — Уоршелла отвечает на это за один раз — с помощью таблицы и трех вложенных циклов. Каждый раунд разрешает еще одну вершину как промежуточную на пути и для каждой пары проверяет, короче ли объезд через нее. Идите по шагам, чтобы увидеть, как заполняется таблица и уменьшаются расстояния. Нажмите Пуск, чтобы посмотреть, как заполняется таблица, или используйте Шаг и Назад, чтобы идти по одному шагу. Перетащите ползунок шагов, чтобы перейти в любое место. В таблице — кратчайшее найденное пока расстояние между каждой парой вершин; число на каждом ребре — его длина. Каждый раунд разрешает еще одну вершину как промежуточную на пути, а каждый шаг показывает пару, которая через нее становится короче. Щелкните вершину, чтобы сделать ее стартом; переключите щелчок на Цель и щелкните другую вершину, чтобы в конце увидеть кратчайший путь между ними. Кнопка Новый граф создает другой граф; выберите, сколько в нем вершин и ребер. Когда поле выбрано, стрелки делают шаг, пробел запускает и ставит на паузу, а Home и End переходят в начало и в конец.
Как это работает
- Нажмите Пуск или используйте Шаг и Назад, чтобы идти по одному шагу. Перетащите ползунок шагов, чтобы перейти в любое место.
- Следите за таблицей: строка и столбец текущей промежуточной вершины подсвечены, а каждый шаг записывает более короткое расстояние.
- Выберите старт и цель, чтобы в конце увидеть кратчайший путь между ними. Кнопка Новый граф создает другой граф для пробы.
Как работает алгоритм Флойда — Уоршелла
Составьте таблицу, в которой на каждую вершину приходится одна строка и один столбец. Запишите 0 на диагонали, длину ребра там, где две вершины соединены, и бесконечность во всех остальных клетках. Затем по очереди берите каждую вершину k как возможную промежуточную. Для каждой пары i, j сравните расстояние от i до j в таблице с расстоянием от i до k плюс расстояние от k до j и оставьте меньшее. После последней вершины каждая клетка — это кратчайшее расстояние между ее двумя вершинами.
Почему это работает
После раунда для k таблица содержит для каждой пары кратчайший путь, все промежуточные вершины которого входят в уже рассмотренные. Раунду для следующей вершины нужно лишь решить, помогает ли она: кратчайший путь через нее — это кратчайший путь до нее плюс кратчайший путь от нее, и оба уже есть в таблице. Такое построение большого ответа из меньших, уже найденных, называется динамическим программированием. С отрицательными ребрами алгоритм тоже работает, а отрицательное число на диагонали выдает отрицательный цикл.
Часто задаваемые вопросы
Что такое алгоритм Флойда — Уоршелла?
Это алгоритм, который находит кратчайшее расстояние между каждой парой вершин во взвешенном графе. Он хранит таблицу расстояний и для каждой вершины по очереди проверяет, не делает ли путь через нее какую-нибудь пару короче.
Насколько быстр алгоритм Флойда — Уоршелла?
В нем три вложенных цикла по n вершинам, поэтому работа растет как n³, а таблице нужно n² клеток. Для графов из нескольких сотен вершин этого достаточно. Для больших разреженных графов быстрее запустить алгоритм Дейкстры из каждой вершины.
Работает ли алгоритм Флойда — Уоршелла с отрицательными ребрами?
Да, если нет отрицательного цикла. Если он есть, какая-то клетка на диагонали становится отрицательной — так алгоритм его и обнаруживает.
Как получить сами пути, а не только расстояния?
Храните вторую таблицу со следующей вершиной на пути от i до j. Каждый раз, когда пара становится короче через k, копируйте следующую вершину на пути от i к k. Идя по этой таблице от i до j, вы получите путь.
Отправляется ли мой граф куда-нибудь?
Нет. Граф создается и таблица заполняется в вашем браузере, а последние настройки хранятся в локальном хранилище этого браузера.
Готовы попробовать?
Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.
Перейти в редактор