🚨 41 lat w przygotowaniu — a Dijkstra nie jest już niepokonany. Zespół z Tsinghua, Stanfordu i MPI for Informatics osiągnął pierwszy deterministyczny algorytm, który łamie granicę O(m + n log n) dla najkrótszych ścieżek z jednego źródła w skierowanych grafach z rzeczywistymi, nieujemnymi wagami. 💡 Nowy czas działania: O(m log^(2/3) n) 📜 Stara najlepsza: Dijkstra + kopiec Fibonacciego = O(m + n log n) Klucz? Hybryda pomysłu „frontier” Dijkstry i relaksacji Bellmana-Forda, z rekurencyjnym trikiem podziału frontu, który utrzymuje kopiec mały — omijając klasyczną barierę sortowania. Wpływ: ⚡ Szybsze przeliczenia GPS 🚦 Płynniejszy ruch drogowy 📦 Tańsze dostawy 🌐 Szybsze routowanie sieci 📚 Czas na przepisanie rozdziału o algorytmach dotyczących SSSP Pierwsze prawdziwe przyspieszenie dla skierowanego SSSP od 1984 roku — i jest deterministyczne.