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

В теме Графы и маршруты · Учебная карта
Главная мысль
Алгоритм Флойда — Уоршелла ищет расстояния между всеми парами вершин. На очередном этапе разрешается новая промежуточная вершина k: прежний путь сравнивается с суммой путей из i в k и из k в j.
Сначала договоримся о смысле клетки
Пусть из А в Б ведёт дуга веса 6, из Б в В — веса −2, а напрямую из А в В — веса 9. Обратных дуг нет. В начале таблица хранит веса непосредственных переходов: клетка А→В равна 9, а В→А недостижима.
На диагонали учитываем нулевой путь без движения. Если задана петля, берём минимум нуля и её веса: отрицательную петлю нельзя затереть нулём. Отсутствующую дугу обозначаем бесконечностью, а не нулём. Иначе алгоритм начнёт находить бесплатные переходы там, где их вообще не было. При нескольких дугах одного направления берём наименьший вес.
Пример
Через Б расстояние А→В становится 6+(−2)=4.
Новое значение меньше прямого веса 9. Но В→А остаётся недостижимым: разрешение промежуточной вершины не обращает направления дуг.
Почему промежуточная вершина должна быть снаружи
Представим, что вершины допускаются по одной в порядке А, Б, В. После этапа Б таблица уже учитывает пути, у которых внутри встречаются только А и Б. Для каждой пары сравниваем прежнее расстояние и вариант через Б. Это и есть смысл этапа, а не просто три произвольно вложенных цикла.
Проверять все пары нужно при каждом новом k. Если без доказательства поменять порядок циклов и сделать k внутренним, одно прохождение перестанет соответствовать этому правилу. Удобная ручная проверка — цепочка из четырёх вершин с единственным направлением: дальний конец должен стать достижимым из начала независимо от названий. Чтобы показать сам маршрут, вместе с расстояниями сохраняют сведения о переходах: одна итоговая сумма не позволяет восстановить посещённые вершины однозначно.
Где заканчивается обычное расстояние
Отрицательная дуга сама по себе допустима. Другое дело — отрицательный цикл: его можно проходить многократно и всё уменьшать вес. Если такой цикл достижим из i и из него можно попасть в j, конечного кратчайшего расстояния для этой пары нет.
Отрицательная диагональная клетка после вычисления сигнализирует о таком цикле. Нельзя просто напечатать все получившиеся числа как окончательные ответы. В реализации также нельзя складывать специальную отметку недостижимости с обычным весом как будто это конечное число. Для n вершин таблица занимает порядка n² клеток, обновления — порядка n³ операций.
От чтения к действию
А теперь — вы
Частые вопросы
Нужно ли превращать отрицательные веса в положительные?
Нет: прибавление константы к каждой дуге меняет сравнение путей с разным числом рёбер. Отрицательные веса разрешены; отдельно учитываются отрицательные циклы.
Чем это отличается от одного запуска поиска пути?
Здесь результат содержит все начальные и конечные вершины. Если нужен один источник в большом разреженном графе, такая полная таблица может быть избыточной.
Источники и работа с материалом
Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.
Продолжить разбираться
Как ослабление рёбер работает с отрицательными весами
Разбираем последовательное улучшение расстояний, влияние порядка рёбер и проверку достижимого отрицательного цикла на собственном примере.
Открыть темуКогда список смежности выгоднее матрицы
Сравниваем список смежности и матрицу по памяти и операциям, сохраняем направление и вес рёбер и выбираем структуру под разреженность и требуемые запросы.
Открыть тему