Hacker News Digest

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

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

Команда исследователей предложила новый алгоритм, который обходится без сортировки и работает быстрее всех «сортирующих» методов, преодолев сорокалетний барьер. Роберт Тарьян назвал результат поразительным.

Графы описывают вершины и ребра с весами (длина, время и т.п.). Задача: по данному источнику найти кратчайшие пути до всех вершин. Алгоритм Дейкстры (1956) идет «волной» наружу: зная оптимальные пути к ближайшим, находит пути к дальним. Но конечный результат — упорядоченный набор кратчайших расстояний, и потому скорость ограничена сортировкой. В 1984 году Тарьян с соавтором улучшили Дейкстру до этого предела: чтобы ускориться дальше, нужно избегать сортировки.

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

Идея Дуани (созревшая к 2021 году): вместо того чтобы на каждом шаге сканировать всю «границу» уже исследованной области, как делает Дейкстра (что со временем замедляет ход), группировать соседние граничные вершины в кластеры и рассматривать по одному представителю из каждого. Это уменьшает число кандидатов и может вести не к ближайшей вершине — значит, зависимость от сортировки исчезает. Главная трудность — доказать, что кластеризация действительно ускоряет процесс на каждом шаге и в сумме.

За следующий год Дуань проработал идею и к осени 2022-го был уверен, что технические барьеры преодолимы.

• Обсуждение вокруг нового алгоритма SSSP с детерминированной сложностью O(m log^(2/3) n), который улучшает Дейкстру на разреженных графах; ссылку дали на arXiv: 2504.17033.
• Участники отмечают, что выигрыш зависит от структуры графа: для дорожных сетей обычно m ≈ c·n (c ~ 4–6 для ориентированных), что даёт O(n log^(2/3) n); для очень плотных графов (m ~ n^2) преимущество может исчезать.
• Возникают вопросы о сравнении логарифмических степеней, применимости к задачам вроде TSP с почти полными графами, и сохранении гарантии глобального минимума как у Дейкстры.
• Некоторые считают алгоритм сложнее Дейкстры, но отмечают теоретическую значимость прорыва и отсутствие «фancy math», что делает результат удивительным.
• Обсуждают возможные гибриды с рандомизацией и практическое влияние на реальные графы (улицы, геймдев).
• Есть скепсис о «позднем открытии» и комментарии про то, что практики могли бы дойти до подобных идей, но не оформляют их академически.
• Вспоминают вклад классиков (Тарjan и др.) и проводят аналогию с TimSort: практичная оптимизация поверх классики.