41 yıl sonra yeni bir en kısa yol algoritması keşfedildi

Ç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.

[slowmo]

2000’lerin sonlarında araç navigasyon yazılımı şirketinde çalışırken rota arama modülü geliştirdiğim günlerin anısı(?) aklıma geliyor. Dijkstra, navigasyon rota aramasında kullanılmayacak kadar yavaş olduğu için tercih edilmiyor; bunun yerine sezgisel olarak iyileştirilmiş sürümü olan A* (A Star) araması kullanılıyor. Araştırınca A*’ın SSSP değil, SPSP (Single-Pair Shortest Path) algoritması olduğunu gördüm.

[qpalzmxn]

Seyrek durumlarda hızlı algoritmaları da aştığını söylemek biraz muğlak görünüyor.

[helio]

CLRS'in revize edilmesinin üzerinden çok da uzun zaman geçmemiş olmalı; şimdi yeni baskı mı yapılıyor?

[kmc0722]

Geçmişte ortaya çıkıp bugün hâlâ popüler olan Beatles ya da Oasis'in 41 yıl sonra yeni albüm çıkarmış gibi hissettiriyor. Öncelikle şaşkınlık ve merak uyandırıyor, haha

[brainypooh]

ABD'de belki zaten vardı? vay canına

[devstudyman7]

Ne kadar da güzelmiş, vay canına.

[ahwjdekf]

Çin son zamanlarda gerçekten öne çıkıyor.

[onetoday]

Algoritmanın adının nasıl belirleneceğini merak ediyorum.

[belline0124]

Yakında biri bu kısıtlarla Baekjoon'da bir problem çıkarır herhalde, heyecanlandım.

[fastkoder]

Nostaljik Dijkstra..

[chebread]

Vay be... inanılmaz...

[channprj]

Harika.

[woogi]

Vay be......

[pmc7777]

Bu oluyormuş...

[kimjoin2]

Vay be~~

[roxie]

Vay be....

[beoks]

Algoritma derslerinin içeriğine eklenecek gibi görünüyor hahaha

[jhk0530]

Vay canına...