Breaking the sorting barrier for directed single-source shortest paths
Если хотите решить сложную задачу, полезно разложить ее на части и идти от простого к сложному. Но сортировка частей тоже стоит времени: можно потратить его больше на упорядочивание, чем на решение.
Это особенно заметно в культовой задаче информатики — поиске кратчайших путей от одной вершины графа до всех остальных. Интуитивно проще сначала находить ближайшие цели, затем более дальние. Но для этого нужно постоянно определять, какая вершина ближе, то есть фактически сортировать по расстоянию. Возникает «барьер сортировки»: алгоритм, зависящий от сортировки, не может быть быстрее, чем сама сортировка.
Команда исследователей предложила новый алгоритм, который обходится без сортировки и работает быстрее всех «сортирующих» методов, преодолев сорокалетний барьер. Роберт Тарьян назвал результат поразительным.
Графы описывают вершины и ребра с весами (длина, время и т.п.). Задача: по данному источнику найти кратчайшие пути до всех вершин. Алгоритм Дейкстры (1956) идет «волной» наружу: зная оптимальные пути к ближайшим, находит пути к дальним. Но конечный результат — упорядоченный набор кратчайших расстояний, и потому скорость ограничена сортировкой. В 1984 году Тарьян с соавтором улучшили Дейкстру до этого предела: чтобы ускориться дальше, нужно избегать сортировки.
В конце 1990-х — начале 2000-х Торуп и другие обошли барьер для частных случаев, вводя ограничения на веса. Обобщить техники на произвольные веса не удавалось, и прогресс застопорился. Ран Дуань не согласился с пессимизмом и стремился сломать барьер для всех графов — и прошлой осенью добился цели.
Идея Дуани (созревшая к 2021 году): вместо того чтобы на каждом шаге сканировать всю «границу» уже исследованной области, как делает Дейкстра (что со временем замедляет ход), группировать соседние граничные вершины в кластеры и рассматривать по одному представителю из каждого. Это уменьшает число кандидатов и может вести не к ближайшей вершине — значит, зависимость от сортировки исчезает. Главная трудность — доказать, что кластеризация действительно ускоряет процесс на каждом шаге и в сумме.
За следующий год Дуань проработал идею и к осени 2022-го был уверен, что технические барьеры преодолимы.