Breaking the Sorting Barrier for Directed Single-Source Shortest Paths
Предложен детерминированный алгоритм времени O(m log^{2/3} n) для задачи кратчайших путей из одного источника (SSSP) во взвешенных ориентированных графах с неотрицательными весами в модели сравнение-сложение. Впервые превзойдена граница O(m + n log n) алгоритма Дейкстры на разреженных графах, что доказывает его неоптимальность для SSSP.
Комментарии (3)
- Обсуждали статью о новом алгоритме для разреженных графов.
- Алгоритм даёт ускорение только при средней степени < 3, если граф не триллионных размеров.
- MarkusQ уточнил: при m < 3n это ≈ степень < 6, так что двумерные решётки всё ещё выигрывают.
- Вывод: улучшение полезно, но не универсально.