Yakın düğümlerde en kısa yol hesabına yeni yaklaşım

Ana sayfa

Bilim

APSP algoritması, 1996'dan beri aşılamayan sınırı geçti. Manoj Gupta'nın yöntemi hızdan ödün vermeden yakın düğümlerde de 2-yaklaşım garantisi veriyor.

02.11.2026 08:44 okunma

Manoj Gupta, ağdaki tüm düğüm çiftleri arasındaki en kısa yolları bulan APSP problemi için 1996'dan beri aşılamayan bir sınırı geçti.

Yeni yöntem, eski algoritma kadar hızlı çalışırken yakın noktalarda da en fazla iki kat hata garantisini koruyor.

Çalışma teorik; ulaşım, telekomünikasyon ve biyolojik ağ analizleri için matematiksel temeli güçlendiriyor.

Hindistan Teknoloji Enstitüsü Gandinagar'da doçent olan Manoj Gupta, grafiklerde en kısa yolları bulan APSP algoritması için önemli bir iyileştirme sundu. APSP, yani All-Pairs Shortest Paths, bir ağdaki tüm düğüm çiftleri arasındaki en kısa yolları hesaplar. Çalışma FOCS 2025 sempozyumunda yayımlandı.

Sonuç, 1996'dan beri ilk kez bir sınırı kaydırıyor. Bu sınırın ötesinde 2-yaklaşım garantisi veriliyordu. Yani tahmin edilen mesafe, gerçek mesafenin en fazla iki katı olabiliyordu. Ancak artık bu garanti birbirine çok daha yakın düğümler için de geçerli.

Eski APSP algoritması neden yetersizdi?

Dor, Halperin ve Zwick (DHZ) o yıl verimli bir yöntem önermişti. Seçilen az sayıda "yön noktası" sayesinde uzun rotalar hızla tahmin ediliyordu. Örneğin Delhi ile Chennai arasındaki yolu bulmak için tüm seçenekleri taramak gerekmiyordu.

Fakat yakın noktalarda işler değişiyordu. Mumbai'deki iki semt gibi çiftlerde yön noktaları çoğu zaman en kısa bağlantıdan uzak kalıyordu. Bu yüzden algoritma gerçekte iki kenarlık yol yerine beş kenarlık bir yol verebiliyordu. Bu da "en fazla 2 kat" garantisini bozuyordu.

Kısacası eski APSP algoritması uzak noktalarda başarılıydı. Buna karşın yakın noktalarda söz verdiği doğruluğu koruyamıyordu. Üç on yıla yakın süre boyunca bu açık kapanmadı.

Yeni APSP algoritması nasıl çalışıyor?

Gupta, noktaların seçilme biçimini baştan kurguladı. Tek katmanlı yön noktaları yerine ağı çok seviyeli temsil eden bir yapı kullanıyor. Böylece bağlantılar aynı anda birden fazla ölçekte inceleniyor.

Bu sayede eski yöntemin gözden kaçırdığı kısa rotalar yakalanıyor. Üstelik hesaplama karmaşıklığı artmıyor. Kısacası yeni APSP algoritması eskisi kadar hızlı, ama kısa mesafelerde de güvenilir çalışıyor.

Neden önemli?

Etkisi yalnızca navigasyon uygulamalarıyla sınırlı değil. APSP problemi ulaşım sistemlerinin, telekomünikasyon ağlarının ve hatta protein etkileşimleri ile sinir bağlantıları gibi biyolojik yapıların analizinde kullanılıyor.

Büyük grafiklerde tam hesaplama kübik zaman istiyor. Düğüm sayısı iki katına çıkınca işlem yükü yaklaşık sekiz katına çıkıyor. Bu nedenle hız ile kontrollü doğruluğu birleştiren yaklaşık yöntemler, gerçek veri kümeleri için kritik önem taşıyor.

Çalışma teorik nitelikte ve harita servislerine doğrudan entegre edilmiyor. Yine de büyüyen ağları verimli işleyecek yöntemlerin matematiksel temelini güçlendiriyor. Yaklaşık üç on yıldır açık duran sorunun kapanması, APSP algoritması gibi köklü yöntemlerde kademeli iyileştirmelerin hâlâ sınırları genişletebildiğini gösteriyor.

Haberde hata mı var?Bize bildirin

Senin fikrin ne?

Bu gelişme hakkında sen ne düşünüyorsun?

Yorumlar

İlk yorumu siz yazın.