Информатика · объяснение и практика

Как промежуточная вершина обновляет расстояния между всеми парами

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

Синие фигурные скобки держат между собой оранжевый квадрат.

В теме Графы и маршруты · Учебная карта

Главная мысль

Алгоритм Флойда — Уоршелла ищет расстояния между всеми парами вершин. На очередном этапе разрешается новая промежуточная вершина k: прежний путь сравнивается с суммой путей из i в k и из k в j.

Сначала договоримся о смысле клетки

Пусть из А в Б ведёт дуга веса 6, из Б в В — веса −2, а напрямую из А в В — веса 9. Обратных дуг нет. В начале таблица хранит веса непосредственных переходов: клетка А→В равна 9, а В→А недостижима.

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

Пример

Через Б расстояние А→В становится 6+(−2)=4.

Новое значение меньше прямого веса 9. Но В→А остаётся недостижимым: разрешение промежуточной вершины не обращает направления дуг.

Почему промежуточная вершина должна быть снаружи

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

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

Где заканчивается обычное расстояние

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

Отрицательная диагональная клетка после вычисления сигнализирует о таком цикле. Нельзя просто напечатать все получившиеся числа как окончательные ответы. В реализации также нельзя складывать специальную отметку недостижимости с обычным весом как будто это конечное число. Для n вершин таблица занимает порядка n² клеток, обновления — порядка n³ операций.

От чтения к действию

А теперь — вы

Есть дуги М→Н веса 7, Н→О веса −4 и М→О веса 8. Других дуг нет. Каково кратчайшее расстояние М→О?

Частые вопросы

Нужно ли превращать отрицательные веса в положительные?

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

Чем это отличается от одного запуска поиска пути?

Здесь результат содержит все начальные и конечные вершины. Если нужен один источник в большом разреженном графе, такая полная таблица может быть избыточной.

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться