Графы сортировали полвека — пока не пришёл алгоритм, который доказал: зря

Когда перед вами стоит сложная задача, логично попытаться её упростить — например, разбить на части и решить сначала то, что проще. Но у такой стратегии есть издержки: на само разбиение и сортировку может уйти слишком много времени. В задачах, где важна скорость, это может стать критическим фактором.

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

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

Этот предел — так называемый «барьер сортировки» — определяет нижнюю границу для скорости любых алгоритмов, которые идут по пути выбора ближайшей вершины. С начала 1980-х годов казалось, что быстрее уже не получится.

Однако команде исследователей во главе с Жанем Дуаном из Университета Цинхуа удалось построить алгоритм , который обходит это ограничение. Их решение быстрее любого метода, основанного на сортировке. Более того, оно работает как для ориентированных, так и для неориентированных графов с произвольными весами, не требуя специальных допущений.

Алгоритм кратчайших путей ищет на графе — сети из узлов и соединяющих их рёбер с весами — путь от заданной вершины к остальным с минимальной суммой этих весов. Самый известный подход, предложенный Эдсгером Дейкстрой в 1956 году, работает по принципу постепенного расширения известной области от источника. Это даёт эффективные результаты, но упирается в необходимость сортировать вершины по расстоянию, чтобы знать, куда идти дальше.

В 1984 году Роберт Таржан и соавторы улучшили реализацию Дейкстры, приблизившись к теоретическому пределу. Чтобы идти дальше, нужно было отказаться от идеи упорядочивания на каждом шаге.

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

Вдохновлённый работами времён аспирантуры в Мичигане, в 2021 году он начал прорабатывать концепцию, в которой на каждом шаге исследуется не вся граница текущей области, как у Дейкстры, а лишь ограниченное число узлов — по одному из каждого кластера, на которые делится граница. Это уменьшает количество сравнений и теоретически позволяет избежать сортировки.

К 2022 году он был уверен, что идея жизнеспособна, и привлёк трёх студентов для проработки деталей. Вскоре появилась первая рабочая версия, но она охватывала только неориентированные графы — в них рёбра можно проходить в обе стороны, что упрощает навигацию.

Для ориентированных графов, где направление имеет значение, задача сложнее. Связь может быть односторонней, и нужно учитывать, что A может легко дойти до B, а вот обратно — уже нет. Тем не менее, команда продолжила работу, вдохновляясь алгоритмом Беллмана — Форда, который не использует сортировку, но обычно слишком медленный.

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

В 2023 году к команде присоединился Сяо Мао из Стэнфорда. Он предложил способ убрать из алгоритма элемент случайности, который использовался в первых версиях, и построить полностью детерминированную схему. Затем Дуан адаптировал приём из своей более ранней работы 2018 года, где он тоже преодолевал барьер сортировки — но для другой задачи. Это и стало недостающим звеном.

Итоговая версия алгоритма действует послойно, как Дейкстра, но не выбирает строго ближайшие узлы. Вместо этого на каждом шаге она использует упрощённый вариант Беллмана — Форда, чтобы определить, какие точки стоит исследовать в первую очередь, а к остальным возвращается позже. Такой подход нарушает последовательность сортировки и позволяет ускорить работу.

Несмотря на отсутствие сложной математики, все элементы схемы должны работать синхронно. Метод оказался не только быстрее классики, но и пригодным для реального применения. Его успех удивил даже ветеранов теории алгоритмов. «Такое решение могло бы появиться ещё полвека назад», — признал Торуп. — «Но появилось только сейчас — и это делает его ещё более ценным».

Теперь команда работает над упрощением и дальнейшим ускорением алгоритма. Барьер сортировки преодолён, но верхней границы скорости пока не видно. «Я не думаю, что это последний шаг», — отметил Таржан. — «Скорее всего, всё только начинается». Подобные прорывы в оптимизации алгоритмов открывают новые возможности для решения вычислительно сложных задач .