Tim peneliti dari Tsinghua University di Tiongkok, bekerja sama dengan Stanford University, mencapai kemajuan besar dari sisi kompleksitas komputasi untuk masalah jalur terpendek tradisional (single-source shortest path, SSSP). Riset ini memenangkan penghargaan Best Paper di konferensi STOC 2025.
Metode yang secara tradisional paling banyak digunakan adalah algoritma Dijkstra, dengan kompleksitas waktu berbentuk O(m + n log n) (n = jumlah node, m = jumlah sisi).
Suku log n berkaitan dengan priority queue atau sorting, dan selama 40 tahun terakhir belum ada peningkatan yang mampu melampaui bagian ini.
Algoritma baru ini menurunkan kompleksitas waktu menjadi O(m · log^(2/3) n).
Karena log^(2/3) n bertambah lebih lambat daripada log n (artinya kenaikannya lebih kecil dibanding log n), perbedaannya menjadi besar ketika jumlah node sangat besar.
Belum ada komentar.