“Pembuatannya algoritma yang hebat,” kata Erik Demaine, seorang ilmuwan komputer di Massachusetts Institute of Technology. “Algoritmanya sangat cepat, sederhana, dan mudah diimplementasikan.”Untuk menerapkan prosedur ini, Anda perlu memutuskan sistem pengaturan catatan Anda – sebuah struktur data, dalam bahasa ilmu komputer. Itu mungkin terdengar seperti detail teknis kecil, tetapi waktu yang dihabiskan untuk mencari catatan Anda setiap kali Anda perlu mengedit atau menghapus entri dapat memiliki efek besar pada runtime keseluruhan algoritma.Data Dijkstra menggunakan struktur data sederhana yang masih bisa ditingkatkan. Selama beberapa dekade berikutnya, para peneliti mengembangkan yang lebih baik, yang dengan penuh kasih disebut “tumpukan,” di mana beberapa item lebih mudah ditemukan daripada yang lain. Mereka memanfaatkan fakta bahwa algoritma Dijkstra hanya perlu menghapus entri untuk simpul terdekat yang tersisa. “Tumpukan pada dasarnya adalah struktur data yang memungkinkan Anda melakukan ini dengan sangat cepat,” kata Václav Rozhoň, seorang peneliti di Institut Ilmu Komputer, Kecerdasan Buatan, dan Teknologi (INSAIT) di Sofia, Bulgaria.Pada tahun 1984, dua ilmuwan komputer mengembangkan desain tumpukan yang cerdik yang memungkinkan algoritma Dijkstra mencapai batas teoritis, atau “batas bawah,” pada waktu yang diperlukan untuk menyelesaikan masalah jalur terpendek sumber tunggal. Dalam satu arti khusus, versi algoritma Dijkstra ini adalah yang terbaik yang mungkin. Itu adalah kata terakhir tentang versi standar masalah selama hampir 40 tahun. Hal-hal hanya berubah ketika beberapa peneliti mengambil pandangan lebih dekat tentang apa artinya “terbaik.”Perilaku TerbaikPeneliti biasanya membandingkan algoritma dengan mempelajari bagaimana mereka berkinerja dalam skenario terburuk. Bayangkan grid jalan yang paling membingungkan di dunia, lalu tambahkan pola lalu lintas yang sangat membingungkan. Jika Anda bersikeras untuk menemukan rute tercepat dalam keadaan ekstrem ini, versi 1984 dari algoritma Dijkstra dapat dibuktikan tidak terkalahkan.Tetapi semoga, kota Anda tidak memiliki grid jalan terburuk di dunia. Jadi Anda mungkin bertanya: Apakah ada algoritma yang tak terkalahkan di setiap jaringan jalan? Langkah pertama untuk menjawab pertanyaan ini adalah membuat asumsi konservatif bahwa setiap jaringan memiliki pola lalu lintas terburuk. Kemudian Anda ingin algoritma Anda menemukan jalur tercepat melalui tata letak grafik apa pun, dengan asumsi bobot terburuk yang mungkin. Para peneliti menyebut kondisi ini “optimalitas universal.” Jika Anda memiliki algoritma yang secara universal optimal untuk masalah yang lebih sederhana hanya untuk sampai dari satu titik ke titik lain di grafik, itu bisa membantu Anda mengatasi kemacetan lalu lintas pada jam sibuk di setiap kota di dunia.”
