🚨 41 рік у процесі становлення — і Дейкстра більше не є неперевершеним. Команда Цінхуа, Стенфорда та MPI for Informatics досягла першого детермінованого алгоритму для розриву межі O(m + n log n) для найкоротших шляхів з одним джерелом у спрямованих графах з реальними невід'ємними вагами. 💡 Нове середовище виконання: O(m log^(2/3) n) 📜 Старий найкращий: Дейкстра + купа Фібоначчі = O(m + n log n) Що є ключовим? Гібрид ідеї «кордону» Дейкстри та релаксації Беллмана-Форда з рекурсивним трюком «розділ кордону», який тримає купу в крихітному стані — ухиляючись від класичного сортувального бар'єру. Вплив: ⚡ Швидші перерахунки GPS 🚦 Більш плавний потік трафіку 📦 Дешевші поставки 🌐 Швидша маршрутизація мережі 📚 Час переписати розділ алгоритмів на SSSP Перше реальне прискорення для спрямованих SSSP з 1984 року — і це детерміновано.