Алгоритм Флойда-Уоршалла: руководство по собеседованию по программированию

ТЛ;ДР: Алгоритм Флойда-Уоршалла вычисляет кратчайшие пути для всех пар с помощью динамического программирования. Инициализируйте матрицу расстояний из графа, затем для каждой промежуточной вершины k обновите каждую пару с помощью dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]). Он работает во времени O(V³) и пространстве O(V²) и может выявлять отрицательные циклы посредством отрицательных диагональных элементов.

Что такое алгоритм Флойда-Уоршалла?

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

Алгоритм запомнился тем, что он превращает проблему глобального пути в одно решение: для текущей промежуточной вершины k лучший известный путь от i до j лучше, как есть, или путем перехода от i к k, а затем от k к j?

Как определить повторение?

Определим D(k, i, j) как кратчайшее расстояние от i до j, промежуточные вершины которого могут исходить только из первых k вершин. Кратчайший разрешенный путь либо обходит вершину k, сохраняя D(k−1, i, j), либо использует k и разделяется на наилучший разрешенный путь от i до k плюс наилучший разрешенный путь от k до j.

Это дает повторение:

D(k, i, j) = min(D(k−1, i, j), D(k−1, i, k) + D(k−1, k, j))

Поскольку этап k зависит только от значений этапа k-1 совместимым образом, матрицу можно обновить на месте. Это рассуждение также объясняет порядок критического цикла: k должен быть самым внешним циклом. Помещение i или j снаружи меняет инвариант и может неправильно использовать частично разрешенные пути.

Как инициализировать матрицу расстояний?

Создайте матрицу V на V. Установите для dist[i][i] значение 0, установите для ячейки прямого края его вес и используйте бесконечность, если прямого края не существует. Если параллельные края возможны, сохраняйте наименьший прямой вес. Прежде чем добавлять два расстояния, убедитесь, что оба конечны, чтобы датчик бесконечности не переполнился и не создал ложного кандидата.

Как вы проследите за Флойдом-Уоршаллом в интервью?

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

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

Какой псевдокод написать?

Используйте три вложенных цикла с k снаружи:

for k from 0 to V - 1:
  for i from 0 to V - 1:
    for j from 0 to V - 1:
      if dist[i][k] is finite and dist[k][j] is finite:
        dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

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

Каковы временные и пространственные сложности?

Три цикла проверяют каждую комбинацию k, i и j, поэтому время выполнения равно O(V³). Матрица расстояний занимает пространство O(V²). Обновление на месте позволяет избежать трехмерной таблицы, а матрица следующего перехода или предшественника для реконструкции пути добавляет O(V²) больше места.

Метод Флойда-Уоршалла часто привлекателен для скромных плотных графов, поскольку его реализация компактна и предсказуема. Для большого разреженного графа с неотрицательными ребрами запуск Дейкстры из каждого источника может быть более эффективным. Перед выбором всегда сравнивайте требуемый результат, плотность графа, ограничения веса и количество вершин.

Как восстановить реальный кратчайший путь?

Сами по себе расстояния не раскрывают последовательность вершин. Сохраняйте матрицу next[i][j], инициализированную значением j, когда существует прямое ребро от i до j. Всякий раз, когда маршрутизация через k улучшает dist[i][j], установите next[i][j] в next[i][k]. Чтобы восстановить путь, несколько раз перемещайтесь от текущей вершины к next[current][destination], пока не достигнете пункта назначения.

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

Как Флойд-Уоршалл обнаруживает отрицательные циклы?

После завершения алгоритма осмотрите диагональ. Значение dist[v][v] < 0 доказывает, что цикл с отрицательным весом достижим из v и может вернуться в v. Это более эффективно, чем просто поиск отрицательного края; отрицательные ребра могут существовать в графах с совершенно допустимыми кратчайшими путями.

Если интервьюер спрашивает, какие пары затронуты, укажите все i и j, для которых я могу достичь такой вершины v, а v может достичь j. Эти пары могут проходить отрицательный цикл произвольное количество раз, поэтому значение их кратчайшего пути не является конечным.

Когда следует выбрать другой алгоритм кратчайшего пути?

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

Каких ошибок на собеседовании следует избегать?

Не помещайте k внутри другого цикла, не забывайте нули на диагонали, не добавляйте бесконечность без защиты, не путайте отрицательные ребра с отрицательными циклами и не утверждайте, что матричное пространство O(V²) автоматически включает входные данные в каждое представление. Выясните, является ли граф направленным, существуют ли параллельные ребра и нужны ли интервьюеру расстояния, пути или пары, подверженные влиянию цикла.

Попрактикуйтесь в рабочем процессе помощника по кодированию собеседований, сравните алгоритм Беллмана–Форда и просмотрите шпаргалку по сложности Big O.

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

Практикуйте инвариант, а не только циклы

YesToTheOffer может помочь структурировать объяснение кодирования, обосновать его в ваших личных подготовительных заметках, изучить крайние случаи и сохранить стенограмму собеседования для последующего просмотра.