DMMSY (Duan, Mao, Mao, Shu, Yin) algoritması, büyük ölçekli seyrek grafiklerde Tek Kaynaklı En Kısa Yol (SSSP) problemlerini çözmek için tasarlanmış yüksek performanslı bir C99 uygulamasıdır. Bu yeni algoritma, geleneksel küresel öncelik kuyrukları yerine özyinelemeli alt problem ayrıştırmasını kullanarak, SSSP algoritmalarındaki uzun süredir devam eden sıralama engelini aşmaktadır. Bu sayede, karmaşıklık faktörünü $O(\log n)$'den $O(\log^{2/3} n)$'ye düşürerek, özellikle büyük ölçekli veri setlerinde önemli bir performans artışı sağlamaktadır.
Uygulama, sıfır bellek tahsisi (zero-allocation) prensibiyle tasarlanmıştır; önceden ayrılmış çalışma alanları ve dikkatli manuel bellek yönetimi sayesinde çalışma zamanı yükü ortadan kaldırılmıştır. Önbellek optimizasyonlu Sıkıştırılmış Seyrek Satır (CSR) düzeni, maksimum uzamsal yerelliği sağlayarak veri erişimini hızlandırır. Proje, ortak yardımcı programlar, temel Dijkstra algoritması ve optimize edilmiş DMMSY uygulamaları arasında net bir ayrım sunan modüler bir mimariye sahiptir. Ayrıca, platformdan bağımsız, yüksek hassasiyetli zamanlama özellikleri sayesinde istikrarlı performans raporlaması yapabilmektedir.
Yapılan testler, modern x86_64 mimarisinde Clang -O3 derleyicisi ve LTO/Fast-Math optimizasyonları kullanılarak gerçekleştirilmiştir. DMMSY, özellikle 250 bin ila 1 milyonun üzerinde düğüme sahip grafiklerde maksimum performans farkını göstermektedir. C uygulamasındaki yalın DMMSY yürütme mantığı, 1 milyon düğüm için yaklaşık 800 nanosaniye gibi bir sürede geleneksel ikili yığınlarda bulunan sıralama darboğazlarını etkili bir şekilde ortadan kaldırmaktadır. Proje, rastgele seyrek grafikler üreten ve birden fazla algoritma arasındaki performansı karşılaştıran kapsamlı bir kıyaslama paketi sunmaktadır. Açık kaynaklı olup MIT ve Apache 2.0 lisansları altında yayımlanmıştır.
Bu yeni algoritma, büyük ölçekli grafiklerde en kısa yol hesaplamalarında performansı radikal bir şekilde artırarak, veri bilimi ve ağ analizi gibi alanlarda yeni kapılar açıyor.