Versi aslinya dari cerita ini muncul di Majalah Kuanta.
Jika Anda ingin memecahkan masalah yang rumit, mengatur diri sendiri sering kali membantu. Misalnya, Anda dapat memecah masalah menjadi beberapa bagian dan menyelesaikan bagian yang paling mudah terlebih dahulu. Namun penyortiran seperti ini memerlukan biaya. Anda mungkin menghabiskan terlalu banyak waktu untuk menata barang-barang tersebut.
Dilema ini sangat relevan dengan salah satu masalah paling ikonik dalam ilmu komputer: menemukan jalur terpendek dari titik awal tertentu dalam jaringan ke titik lainnya. Ini seperti versi perbaikan dari masalah yang perlu Anda selesaikan setiap kali Anda pindah: mempelajari rute terbaik dari rumah baru Anda ke tempat kerja, gym, dan supermarket.
“Jalur terpendek adalah masalah indah yang dapat dialami oleh siapa pun di dunia,” katanya Mikel Thorupseorang ilmuwan komputer di Universitas Kopenhagen.
Secara intuitif, cara termudah adalah menemukan jalur terpendek ke tujuan terdekat. Jadi jika Anda ingin merancang algoritma tercepat untuk masalah jalur terpendek, masuk akal untuk memulai dengan mencari titik terdekat, lalu titik terdekat berikutnya, dan seterusnya. Namun untuk melakukan itu, Anda perlu berulang kali mencari tahu titik mana yang paling dekat. Anda akan mengurutkan poin berdasarkan jarak seiring berjalannya waktu. Ada batas kecepatan mendasar untuk algoritma apa pun yang mengikuti pendekatan ini: Anda tidak bisa bergerak lebih cepat dari waktu yang diperlukan untuk menyortir.
Empat puluh tahun yang lalu, para peneliti yang merancang algoritma jalur terpendek menghadapi “penghalang penyortiran” ini. Kini, tim peneliti telah merancangnya algoritma baru yang memecahkannya. Itu tidak mengurutkan, dan berjalan lebih cepat daripada algoritma apa pun.
“Para penulisnya berani berpikir bahwa mereka dapat mendobrak penghalang ini,” kata Robert Tarjanseorang ilmuwan komputer di Universitas Princeton. “Ini adalah hasil yang luar biasa.”
Perbatasan Pengetahuan
Untuk menganalisis masalah jalur terpendek secara matematis, peneliti menggunakan bahasa grafik—jaringan titik, atau node, yang dihubungkan oleh garis. Setiap hubungan antar node diberi label dengan angka yang disebut bobot, yang dapat mewakili panjang segmen tersebut atau waktu yang diperlukan untuk melintasinya. Biasanya terdapat banyak rute antara dua node, dan rute terpendek adalah rute yang bobotnya dijumlahkan hingga angka terkecil. Dengan adanya grafik dan node “sumber” tertentu, tujuan algoritma adalah menemukan jalur terpendek ke setiap node lainnya.
Itu algoritma jalur terpendek yang paling terkenal, dirancang oleh ilmuwan komputer perintis Edsger Dijkstra pada tahun 1956, dimulai dari sumbernya dan bekerja secara bertahap. Ini merupakan pendekatan yang efektif, karena mengetahui jalur terpendek ke node terdekat dapat membantu Anda menemukan jalur terpendek ke node yang lebih jauh. Namun karena hasil akhirnya adalah daftar jalur terpendek yang diurutkan, penghalang pengurutan menetapkan batasan mendasar pada seberapa cepat algoritme dapat berjalan.
