“Ini adalah algoritma yang hebat,” kata Erik Demaine, ilmuwan komputer di Massachusetts Institute of Technology. “Ini sangat cepat, sederhana, dan mudah diterapkan.”
Untuk menerapkan prosedur ini, Anda perlu memutuskan sistem untuk mengatur catatan Anda—struktur data, dalam istilah ilmu komputer. Ini mungkin terdengar seperti detail teknis kecil, namun waktu yang dihabiskan untuk menelusuri catatan Anda kapan pun Anda perlu mengedit atau menghapus entri dapat berdampak besar pada keseluruhan waktu proses algoritme.
Makalah Dijkstra menggunakan struktur data sederhana yang masih memberikan ruang untuk perbaikan. Pada dekade-dekade berikutnya, para peneliti mengembangkan tumpukan yang lebih baik, yang disebut “tumpukan”, yang mana benda-benda tertentu lebih mudah ditemukan dibandingkan benda-benda lainnya. Mereka memanfaatkan fakta bahwa algoritma Dijkstra hanya perlu menghapus entri untuk simpul terdekat yang tersisa. “Heap pada dasarnya adalah struktur data yang memungkinkan Anda melakukan ini dengan sangat cepat,” kata Václav Rozhoň, peneliti di Institut Ilmu Komputer, Kecerdasan Buatan, dan Teknologi (INSAIT) di Sofia, Bulgaria.
Pada tahun 1984, dua ilmuwan komputer mengembangkan desain heap cerdas yang memungkinkan algoritma Dijkstra mencapai batas teoritis, atau “batas bawah,” pada waktu yang diperlukan untuk memecahkan masalah jalur terpendek satu sumber. Dalam satu hal tertentu, versi algoritma Dijkstra ini adalah yang terbaik. Itu adalah kata terakhir pada versi standar masalah ini selama hampir 40 tahun. Segalanya berubah ketika beberapa peneliti melihat lebih dekat apa artinya menjadi “terbaik.”
Perilaku Terbaik
Para peneliti biasanya membandingkan algoritma dengan mempelajari bagaimana kinerjanya dalam skenario terburuk. Bayangkan jaringan jalan yang paling membingungkan di dunia, lalu tambahkan beberapa pola lalu lintas yang sangat membingungkan. Jika Anda bersikeras mencari rute tercepat dalam keadaan ekstrem ini, algoritma Dijkstra versi 1984 terbukti tidak ada duanya.
Namun mudah-mudahan, kota Anda tidak memiliki jaringan jalan terburuk di dunia. Jadi Anda mungkin bertanya: Apakah ada algoritma yang tidak ada duanya di setiap jaringan jalan raya? Langkah pertama untuk menjawab pertanyaan ini adalah membuat asumsi konservatif bahwa setiap jaringan mempunyai pola lalu lintas kasus terburuk. Kemudian Anda ingin algoritme Anda menemukan jalur tercepat melalui tata letak grafik apa pun, dengan asumsi bobot terburuk. Para peneliti menyebut kondisi ini sebagai “optimalitas universal”. Jika Anda memiliki algoritme yang optimal secara universal untuk masalah sederhana yaitu berpindah dari satu titik ke titik lain pada grafik, ini dapat membantu Anda mengatasi lalu lintas jam sibuk di setiap kota di dunia.
