Algoritme Dijkstra, dinamai dari penemunya Edsger W. Dijkstra, adalah salah satu algoritma paling fundamental dan banyak digunakan dalam ilmu komputer, khususnya dalam bidang teori graf. Algoritma ini dirancang untuk menemukan jalur terpendek dari satu simpul sumber (source node) ke semua simpul lain dalam graf berbobot (weighted graph), di mana semua bobot tepi (edge weights) haruslah non-negatif.
Konsep jalur terpendek ini sangat krusial dalam berbagai aplikasi dunia nyata, mulai dari sistem navigasi GPS, routing jaringan komputer, hingga pemodelan logistik. Efisiensi dan keandalannya menjadikannya patokan utama sebelum beralih ke algoritma yang lebih kompleks seperti Bellman-Ford (yang menangani bobot negatif) atau A* (yang menggunakan heuristik).
Ilustrasi sederhana graf berbobot yang dianalisis oleh Dijkstra.
Inti dari algoritma Dijkstra adalah pendekatan serakah (greedy approach). Algoritma ini secara iteratif membangun set simpul yang jaraknya sudah diketahui secara pasti dari simpul sumber. Proses ini dilakukan dengan memilih simpul yang belum dikunjungi yang memiliki jarak terpendek sementara dari sumber.
Kinerja Algoritme Dijkstra sangat bergantung pada efisiensi dalam langkah 2: menemukan simpul yang belum dikunjungi dengan jarak terpendek. Jika implementasi sederhana menggunakan array, pencarian ini memakan waktu O(V), menghasilkan kompleksitas total O(V^2) (di mana V adalah jumlah simpul).
Namun, untuk graf yang lebih besar dan jarang (sparse), penggunaan Priority Queue (Antrian Prioritas) berbasis Min-Heap sangat disarankan. Dengan Min-Heap, operasi ekstraksi simpul terpendek hanya memakan waktu O(log V). Karena operasi ini dilakukan untuk setiap tepi (E) dalam proses relaksasi, kompleksitas waktu algoritmik menjadi jauh lebih baik, yaitu O((E + V) log V).
Hal yang paling penting untuk diingat tentang Dijkstra adalah asumsinya mengenai bobot tepi. Algoritma ini secara inheren berasumsi bahwa tidak ada siklus negatif (negative cycles) dan, yang lebih penting, tidak ada bobot tepi negatif. Jika graf mengandung bobot negatif, hasil yang diberikan oleh Dijkstra tidak dapat dijamin benar karena sifat serakahnya.
Mengapa bobot negatif menjadi masalah? Bayangkan sebuah jalur dari A ke B memiliki bobot 10. Dijkstra mencatatnya. Jika kemudian ditemukan jalur melalui C yang memiliki bobot -5, ini akan mengubah struktur jalur terpendek secara drastis, namun Dijkstra mungkin sudah mengunci keputusan pada jalur 10 sebelumnya tanpa kemungkinan untuk "mengoreksi" dirinya secara efektif ketika bobot negatif tersebut baru ditemukan jauh di kemudian hari dalam proses relaksasi.
Dalam kasus bobot negatif, algoritma yang lebih sesuai adalah Algoritme Bellman-Ford, yang memiliki kompleksitas O(VE) namun mampu mengatasi batasan ini.
Algoritme ini adalah tulang punggung dari banyak sistem modern:
Secara keseluruhan, pemahaman mendalam tentang Algoritme Dijkstra adalah prasyarat bagi siapa pun yang bekerja dengan analisis graf, optimasi rute, atau desain sistem jaringan yang efisien.