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