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