Widget HTML #1


Beranda / dijkstra

Dijkstra dikalahkan setelah 40 tahun

webmaster


Apa yang Sebenarnya Terjadi?

Dijkstra tidak “dikalahkan” secara pribadi. Yang terjadi adalah algoritma shortest path klasik—Dijkstra’s Algorithm—yang telah menjadi standar sejak 1956, akhirnya mendapat penantang serius dalam teori algoritma.

Pada tahun 2025, sekelompok peneliti dari Tsinghua University (dipimpin Ran Duan) menemukan algoritma baru yang secara teoretis lebih cepat daripada Dijkstra, khususnya pada graf sparse (graf besar dengan tepi sedikit).

Penemuan ini memecahkan “sorting barrier”—batas teoretis yang selama puluhan tahun dianggap tidak bisa dilewati.

Masalah Besarnya: “Sorting Barrier”

Inti dari Dijkstra adalah:

  1. Menyimpan jarak sementara ke semua node.
  2. Selalu memilih node dengan jarak paling kecil (priority queue).
  3. Proses pemilihan tersebut pada dasarnya setara dengan sorting, atau minimal sangat tergantung pada kecepatan struktur data mirip sorting.

Akibatnya:

  • Kompleksitas Dijkstra: O(m + n log n)
    (m = edges, n = nodes)

Para ahli algoritma selama 40+ tahun percaya bahwa ini adalah batas minimal untuk algoritma shortest-path deterministik.

Terobosan Tsinghua 2025

Tim Tsinghua berhasil menemukan cara menghindari proses sorting penuh, dengan teknik:

  • Recursive graph partitioning
  • Hybrid Dijkstra & Bellman-Ford ideas
  • Clustering nodes secara hierarkis
  • Mengurangi jumlah operasi yang memerlukan prioritas tinggi

Hasilnya:

Kompleksitas baru: O(m log^(2/3) n)

Ini secara teoretis lebih cepat pada graf sparse modern seperti:

  • Jaringan jalan (GPS)
  • Routing internet
  • Jaringan logistik skala besar

Untuk konteks:
log^(2/3) n itu lebih kecil daripada log n, sehingga algoritma baru lebih unggul.

Pengakuan Internasional

Makalah ini memenangkan:

Best Paper Award STOC 2025

(STOC = Symposium on Theory of Computing, konferensi paling bergengsi untuk teori algoritma)

Ini menunjukkan bahwa komunitas ilmiah menganggapnya lompatan besar, bukan sekadar perbaikan kecil.

Dampak bagi Dunia Nyata

1. GPS lebih cepat menghitung rute

Pada jaringan jalan besar (puluhan juta node), setiap pengurangan logaritmik sangat berarti.

2. Internet routing lebih efisien

Jaringan BGP mengelola ratusan ribu prefix; algoritma baru dapat mempercepat rekalkulasi rute ketika ada perubahan.

3. Optimasi logistik

Perusahaan besar (Amazon, Alibaba) dapat menghitung rute distribusi atau jalur robot secara lebih efisien.

4. Algoritma graf generasi baru

Paper ini bisa memicu penelitian lanjutan untuk memecahkan batas teoritis lain yang selama ini dianggap mustahil.

Apakah Dijkstra akan digantikan?

  • Belum.
    Dijkstra tetap mudah dipahami, mudah diimplementasikan, dan cepat untuk graf kecil/menengah.

  • Tapi dalam skala raksasa (jutaan node), algoritma baru ini berpotensi menjadi standar baru setelah implementasinya matang.

Intinya

  • Dijkstra’s algorithm masih sangat berguna.
  • Namun, tahun 2025 menandai terobosan teoretis besar yang akhirnya mengalahkan batas kecepatannya pada graf tertentu.
  • Ini adalah momen bersejarah dalam dunia algoritma—mirip dengan menemukan teknik baru yang memotong kompleksitas setelah puluhan tahun buntu.