Çin'deki Tsinghua University araştırmacıları, Stanford University ile iş birliği yaparak geleneksel tek kaynaklı en kısa yol (single-source shortest path, SSSP) problemi için hesaplama karmaşıklığı açısından büyük bir ilerleme kaydetti. Bu çalışma, 2025 STOC konferansında Best Paper ödülünü kazandı.
Geleneksel olarak en yaygın kullanılan yöntem Dijkstra algoritmasıdır ve zaman karmaşıklığı O(m + n log n) biçimindedir (n = düğüm sayısı, m = kenar sayısı).
log n terimi, öncelik kuyruğu (priority queue) veya sıralama (sorting) ile ilgili kısımdan gelir ve son 40 yıldır bu bölümün ötesine geçen bir iyileştirme olmamıştı.
Yeni algoritma zaman karmaşıklığını O(m · log^(2/3) n) seviyesine düşürdü.
log^(2/3) n, log n'den daha yavaş arttığı için (yani log n'den daha küçük büyüdüğü için), düğüm sayısı çok büyük olduğunda fark belirginleşiyor.
Henüz yorum yok.