Активное развитие алгоритмики позволило совершить серьёзный технологический скачок. Основатель «Школы траблшутеров» Олег Брагинский и ученик Владислав Иванов изучают один из базовых методов, лёгших в основу многих логистических задач.
Вторая половина двадцатого века стала временем открытий и смелых экспериментов в теории алгоритмов. Известности добились Прим, Дейкстра, Краскал, Хаффман. Наработки корифеев востребованы по сей день: помогают в транспортном планировании, архивировании и анализе больших данных.
Параллельно информатик Стивен Уоршелл и исследователь вычислительных систем Роберт Флойд трудились над поиском оптимальных решений при работе с ЭВМ и графами. Учёные стремились эффективно рассчитывать все кратчайшие пути в ориентированных и плотных структурах, в том числе с отрицательными весами рёбер.
Ориентированный граф – совокупность вершин, где рёбра (соединения) задают направление движения. Плотный может совпадать с ориентированным, но отличается максимальным количеством связей у каждого узла.
Особенностью метода Флойда-Уоршелла стало применение динамического программирования. Приём позволяет обойтись без жадных алгоритмов и перебора brute force: дробить задачу на меньшие шаги, находить ответ для каждой части, сопоставлять полученное и собирать итог. Промежуточные значения сохраняются во избежание повторного счёта.
Расчёт происходит в матричном виде и отвечает на вопрос: станет ли путь между парой точек i и j короче, если пройти через вершину k?
Дан граф из четырёх вершин. Часть объединена рёбрами с весами, показанными на изображении ниже. Обратите внимание: стрелки указывают направление – перемещаться в обратную сторону нельзя.
Справа от графа приведена базовая матрица D(0) путей всех вершин. Несвязанным парам стоит присваивать значение настолько большое, чтобы алгоритму было невыгодно рассматривать вариант. Иначе вычисления исказятся, а при отсутствующем элементе программа способна дать сбой. Привычно в подобных ситуациях ставить знак бесконечности «∞».
Теперь проанализируем узлы графа, начиная с нулевого (матрица D(1)) и заканчивая третьим (матрица D(4)). Проверяем, как меняется расстояние при включении очередной точки. Например, добавление вершины 0 в путь 1–2 даёт сумму рёбер, равную 14. А маршрут 1–3 через 0 составит 13, что длиннее прямого перехода.
По аналогии сформируем матрицы для остальных вершин:
Матрица D(4) оказывается финальной: содержит минимальные дистанции между узлами. Оценивая каждую пару с подстановкой новой вершины, получаем ответ для всего графа.
Перечень кратчайших маршрутов получается следующим:
По быстродействию алгоритм Флойда-Уоршелла демонстрирует кубическую зависимость: T = n³, где T – время работы, n – количество вершин. Для графа с 10 узлами расчёты займут 1’000 условных единиц, для 20 – 8’000. Требования к памяти растут по квадрату: Q = n², где Q – занимаемый объём.
Алгоритм Флойда-Уоршелла используется в навигационно-логистических системах при создании схем перемещения людей и товаров: например, для построения оптимального маршрута посетителей торгового центра или доставки в пределах городского района.
Также метод полезен в анализе взаимосвязей пользователей социальных сетей для оценки влияния, расчёте каналов передачи данных между узлами, изучении белковых структур и метаболических цепочек в организмах. В играх подобный инструмент помогает юнитам и NPC (non-playable characters) прокладывать путь по карте.