Математики превзошли классический алгоритм поиска пути в графе

Математики разработали новый алгоритм поиска кратчайшего пути в графе, который превосходит классический алгоритм.
Новый алгоритм не использует сортировку и работает быстрее, чем другие алгоритмы с сортировкой.
Исследователи использовали язык графов для математического анализа проблемы поиска кратчайших путей.
Алгоритм Дейкстры является известным алгоритмом кратчайшего пути, но имеет фундаментальное ограничение скорости из-за сортировки.
В 1980-х годах Тарьян и другие исследователи усовершенствовали алгоритм Дейкстры, но не смогли преодолеть барьер сортировки.
Ран Дуань, информатик из Университета Цинхуа, разработал алгоритм, преодолевающий барьер сортировки на всех графах, в 2021 году.
Дуань сосредоточился на том, куда алгоритм переходит на каждом шаге, и сгруппировал соседние узлы на границе в кластеры.
Новый алгоритм работает быстрее, чем лучшая версия алгоритма Дейкстры, и не упирается в барьер сортировки.