Algoritma jalur terpendek baru ditemukan setelah 41 tahun

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.

[slowmo]

Ini mengingatkan saya pada kenangan(?) saat bekerja di perusahaan software navigasi kendaraan pada akhir 2000-an dan mengembangkan modul pencarian rute.
Dijkstra terlalu lambat untuk pencarian rute navigasi sehingga tidak digunakan, dan sebagai gantinya dipakai pencarian A* (A Star), versi dengan heuristik yang ditingkatkan. Setelah saya cek, ternyata A* bukan algoritma SSSP melainkan SPSP (Single-Pair Shortest Path).

[qpalzmxn]

Kalau dibilang berhasil melampaui algoritma yang cepat untuk kasus yang sparse, rasanya agak meragukan.

[helio]

CLRS baru direvisi belum lama ini, apakah akan dicetak ulang lagi?

[kmc0722]

Rasanya seperti album baru dari The Beatles atau Oasis, band yang muncul di masa lalu dan masih populer hingga sekarang, setelah 41 tahun. Pertama-tama, ini benar-benar mengejutkan dan membangkitkan minat, haha.

[brainypooh]

Mungkin Amerika sudah punya? ngeri juga

[devstudyman7]

Indah sekali, gila sih

[ahwjdekf]

Tiongkok belakangan ini memang melesat.

[onetoday]

Kira-kira bagaimana nama algoritmenya akan ditentukan ya

[belline0124]

Sebentar lagi pasti ada yang membuat soal di Baekjoon dengan batasan itu, deg-degan.

[fastkoder]

Nostalgia Dijkstra..

[chebread]

Wah... luar biasa...

[channprj]

Keren.

[woogi]

Wow......

[pmc7777]

Ini ternyata bisa...

[kimjoin2]

Wih~~

[roxie]

Wih....

[beoks]

Sepertinya materi kuliah algoritma bakal bertambah, wkwkwk

[jhk0530]

Aduh...