TLDR
Algoritma baru yang dikembangkan oleh Ran Duan dapat mengatasi penghalang penyortiran dalam masalah jalur terpendek. Pendekatan ini menggunakan pengelompokan node untuk meningkatkan efisiensi pencarian jalur terpendek. Inovasi dalam algoritma ini menunjukkan bahwa masih ada ruang untuk penemuan baru dalam teori graf. Masalah menemukan jalur terpendek dalam jaringan sudah lama menjadi tantangan penting di ilmu komputer. Algoritma klasik seperti Dijkstra yang ditemukan sejak tahun 1956, secara intuitif memasukkan pengurutan node berdasarkan jarak, tapi menghadapi batas kecepatan akibat proses tersebut.Peneliti seperti Robert Tarjan dan yang lainnya telah lama mengetahui bahwa ada batas kecepatan fundamental, yaitu sorting barrier, yang sulit dilampaui oleh algoritma berbasis pengurutan. Dalam dekade terakhir, upaya melampaui batas ini terkendala oleh asumsi tertentu atau terbatas pada jenis graf tertentu.Ran Duan dan timnya di Universitas Michigan berhasil mengembangkan algoritma baru yang menghindari pengurutan dengan menggunakan pengelompokan node dan pendekatan yang mengombinasikan algoritma Bellman-Ford secara selektif. Pendekatan ini secara bertahap memecahkan masalah pada graf tanpa arah.Kemudian, dengan bantuan Xiao Mao, mereka membuat versi tanpa elemen acak yang membuat algoritma lebih stabil dan dapat diaplikasikan ke graf berarah yang lebih kompleks. Ini menandai lompatan besar dalam menyelesaikan masalah jalur terpendek secara lebih efisien.Meskipun algoritma ini lebih rumit dibanding Dijkstra, hasilnya sedikit lebih cepat dan membuka banyak peluang untuk perbaikan lebih lanjut. Penemuan ini menghilangkan batasan lama dan diharapkan terus dikembangkan untuk hasil yang bahkan lebih optimal.
