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