31 Temmuz 2025’te yayımlanan “Breaking the Sorting Barrier for Directed Single-Source Shortest Paths” başlıklı araştırma, bilgisayar bilimlerinde önemli bir sıralama engelini aşıyor. Bu çalışma, deterministik olarak yönlü ve gerçek ağırlıklı graf’larda tek kaynaklı en kısa yol (SSSP) problemini çözmede O(m log²⁄³ n) zaman karmaşıklığına ulaşan ilk algoritmayı sunuyor. Bu, yönlü graf’larda kısa yol hesaplamada Dijkstra’nın 66 yıllık hız sınırını aşıyor. O(m log²⁄³ n) karmaşıklığıyla “sorting barrier” resmen yıkılmış durumda.
Sıralama Engeli: Yılların Duvarı
1959’da Edsger Dijkstra tarafından geliştirilen klasik algoritma, O(m + n log n) karmaşıklığıyla uzun süre “hız rekorunu” elinde tuttu. Ancak bu yöntem, düğümleri uzaklığa göre sıralama ihtiyacı nedeniyle Ω(n log n) alt sınırına takılıyordu.
Bu “sorting barrier” (sıralama engeli), özellikle:
- Seyrek (sparse) graf’larda,
- Gerçek zamanlı rota hesaplama, ağ optimizasyonu, robotik gibi uygulamalarda,
performansın önünde büyük bir engeldi.
Araştırmanın Teknik Katkısı
Yeni algoritma, Dijkstra ve Bellman-Ford prensiplerini birleştirerek ön cephe (frontier) küçültme yaklaşımıyla sıralama engelini aşıyor.
Temel Parametreler
- k = ⌊log¹⁄³ n⌋, t = ⌊log²⁄³ n⌋ olarak seçiliyor.
- Sabit dereceye dönüştürülmüş yönlü graf’lar üzerinde çalışıyor (constant-degree transformation).
- Comparison-addition model içinde yalnızca karşılaştırma ve toplama işlemlerine izin veriliyor.
Çekirdek Fikir
- “Ön cephe” adı verilen aktif düğüm kümesi üzerinden çalışılır.
- FindPivots adımıyla bu küme küçültülerek yalnızca “kritik” düğümler (pivotlar) işlenir.
- Dijkstra gibi tüm düğümleri sıralamak yerine, yalnızca mesafesi belirlenmesi gereken alt kümeler işlenir.
- Bounded Multi-Source Shortest Path (BMSSP) alt rutiniyle alt sınırlar (B) üzerinden böl ve fethet yaklaşımı uygulanır.
Bu tekniklerle, algoritma O(m log²⁄³ n) zamanında çalışır, bu da Dijkstra’nın teorik alt sınırını aştığı anlamına gelir.
Bilgisayar biliminde kısa yol problemleri (Single-Source Shortest Path – SSSP), onlarca yıldır araştırmacıların üzerinde çalıştığı temel konulardan biridir. Özellikle Dijkstra algoritması, 1959’dan bu yana hem ders kitaplarının hem de uygulamaların vazgeçilmez yöntemlerinden biri olmuştur. Ancak bu klasik algoritmanın O(m + n log n) zaman karmaşıklığı, özellikle seyrek (sparse) graf yapılarında bir “sıralama engeli” (sorting barrier) olarak biliniyordu.
Yakın zamanda geliştirilen yeni bir yöntem, bu engeli yönlü ve ağırlıklı graf’lar üzerinde kırarak O(m log²⁄³ n) gibi etkileyici bir süreye ulaşmayı başardı. Bu, yalnızca hız açısından değil, deterministik (yani tamamen rastgelelikten bağımsız) olması açısından da bir ilk niteliği taşıyor.
Sıralama Engeli Nedir ve Neden Önemli?
Çoğu kısa yol algoritması, düğümleri kaynaktan olan uzaklıklarına göre sıralamayı gerektirir. Dijkstra algoritması, öncelik kuyruğu (priority queue) kullanarak her adımda en kısa mesafedeki düğümü seçer. Bu işlem, pratikte “sıralama” ile eşdeğerdir ve sıralama işleminin teorik alt sınırı olan Ω(n log n) karmaşıklığını aşmak mümkün değildir.
Bu “sıralama engeli” şunlara yol açar:
- Büyük veri setlerinde performans sınırlaması
- Gerçek zamanlı uygulamalarda gecikme
- Düğümlerin tam sırasının gerekli olmadığı durumlarda bile sıralama maliyetine katlanma
Yeni algoritmanın farkı ise, düğümler arasındaki tam sıralamayı üretmeden yalnızca gerekli mesafeleri hesaplamasıdır.
Yeni Yöntemin Temel Fikri
Araştırmacıların önerdiği yöntem, Dijkstra ve Bellman-Ford algoritmalarının güçlü yönlerini birleştirerek çalışıyor.
- Dijkstra’dan İlham:
- Kaynaktan en kısa mesafeli düğümleri kademeli olarak işleme mantığı korunuyor.
- Bellman-Ford’dan İlham:
- Tüm kenarları topluca rahatlatma (relaxation) tekniği, bazı alt adımların hızlandırılmasında kullanılıyor.
Ana fikir, düğümleri doğrudan sıralamak yerine ön cephe (frontier) adı verilen bir küçük alt küme üzerinde çalışmak. Bu ön cephe, yalnızca hesaplamayı ilerletecek düğümleri içeriyor.
Ön Cephe Küçültme Tekniği
Algoritma, “ön cephe”deki düğüm sayısını azaltmak için pivots (dönüm noktaları) adını verdiği özel düğümleri seçiyor.
- Eğer ilgilenilen düğüm sayısı (Ũ) ön cephe boyutunun k katından fazlaysa, zaten küçük bir oranla çalışılıyor demektir.
- Aksi durumda, Bellman-Ford mantığında birkaç adım çalışarak gereksiz düğümleri “tamamlanmış” hale getirip ön cepheyi küçültüyor.
Bu sayede, tüm düğümleri sıralamak yerine yalnızca kritik olan küçük bir küme üzerinde işlem yapılıyor.
| Algoritma | Zaman Karmaşıklığı | Rastgelelik | Özellik |
|---|---|---|---|
| Dijkstra | O(m + n log n) | Hayır | Basit, yaygın |
| Bellman-Ford | O(mn) | Hayır | Negatif ağırlıkları da destekler |
| Duan-Mao-Mao-Shu-Yin (2025) | O(m log²⁄³ n) | Hayır | Deterministik, sıralama engelini kırar |
Uygulama Alanları
- Harita ve navigasyon sistemleri: Daha hızlı rota hesaplama
- Telekom ağları: Paket yönlendirme optimizasyonu
- Gerçek zamanlı oyun motorları: Dinamik yol bulma
- Robotik ve yapay zeka: Anlık karar verme
