Motivasi

Dijkstra mengembangkan himpunan simpul yang jarak terpendeknya sudah diketahui. Algoritma ini selalu menetapkan simpul terdekat yang belum ditetapkan sebagai final, lalu menggunakannya untuk memperbaiki (melakukan relaksasi pada) jarak ke simpul-simpul tetangganya.

Mengapa mempelajari Dijkstra?

• Digunakan di mana-mana: pencarian rute GPS, perutean paket jaringan, dan pencarian jalur berbiaya paling rendah.
• Greedy yang berhasil: contoh yang jelas tentang pilihan greedy yang terbukti menghasilkan solusi optimal, selama bobotnya tidak negatif.
• Dasar: gagasan relaksasinya muncul kembali dalam A* dan algoritma jalur terpendek lainnya.

Penting: Dijkstra mengasumsikan tidak ada bobot negatif. Sisi negatif memerlukan Bellman-Ford, yang akan dibahas di kursus berikutnya.