Materi
Masalah jalur terpendek mencari lintasan berbobot total terkecil dari satu simpul ke simpul lain di sebuah graf. Kamus algoritma NIST mendefinisikan algoritma Dijkstra sebagai algoritma yang mencari jalur terpendek dari satu simpul sumber ke semua simpul lain pada graf berarah berbobot, dengan syarat semua bobot nonnegatif. Introduction to Computer Science (§3.5) menjelaskan cara kerjanya: algoritma menyimpan antrean prioritas simpul yang diurutkan menurut jarak dari simpul awal, lalu berulang kali mengambil simpul dengan jarak terkecil dan memperluas jalur darinya.
Di Python, antrean prioritas itu tersedia sebagai modul heapq. heapq.heappush(heap, item) memasukkan butir, dan heapq.heappop(heap) mengeluarkan butir terkecil sambil menjaga sifat heap. Dokumentasinya menyarankan tuple (prioritas, tugas) sebagai butir, karena tuple dibandingkan mulai dari elemen pertama. Untuk Dijkstra, butirnya (jarak, simpul).
Langkahnya: jarak awal 0 di simpul sumber, masukkan (0, sumber) ke heap; selama heap berisi, ambil butir terkecil; lewati bila jaraknya sudah usang; untuk setiap tetangga, bila jarak lewat simpul ini lebih kecil daripada jarak yang tercatat, perbarui jaraknya dan masukkan ke heap. Rute lengkapnya disusun dengan mencatat simpul pendahulu, seperti dijelaskan NIST pada entri shortest path.
import heapq
h = []
heapq.heappush(h, (7, "Bogor"))
heapq.heappush(h, (3, "Depok"))
heapq.heappush(h, (5, "Bekasi"))
print(heapq.heappop(h)) # (3, 'Depok'): jarak terkecil keluar lebih dulu