Versi aslinya dari cerita ini muncul di Majalah Kuanta.
Jika Kamu ingin memecahkan masalah yang rumit, mengatur diri sendiri sering kali membantu. Misalnya, Kamu dapat memecah masalah menjadi beberapa bagian dan menyelesaikan bagian yang paling mudah terlebih dahulu. Namun penyortiran seperti ini memerlukan biaya. Kamu 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 Kamu selesaikan setiap kali Kamu pindah: mempelajari rute terbaik dari rumah baru Kamu 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 Kamu 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, Kamu perlu berulang kali mencari tahu titik mana yang paling dekat. Kamu akan mengurutkan poin berdasarkan jarak seiring berjalannya waktu. Ada batas kecepatan mendasar untuk algoritma apa pun yang mengikuti pendekatan ini: Kamu 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 berjumlah paling sedikit. 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 Kamu 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.
