GrafMenengahFase D–FE1E5

Dijkstra Shortest Path

Dijkstra adalah algoritma graf yang mencari rute termurah dari simpul awal ke tujuan pada graf berbobot non-negatif. Ia selalu mengambil simpul dengan jarak sementara terkecil dari antrean prioritas, lalu melakukan relaksasi (memperbarui) jarak ke tetangganya bila ditemukan jalur lebih pendek. Visualisasi menampilkan graf berbobot dengan simpul yang diproses dan jalur optimal yang ditelusuri di akhir.

Contoh kasus

Navigasi Google Maps mencari rute tercepat antar persimpangan pada jaringan jalan.

Silabus

Dijkstra mencari rute termurah pada graf berbobot non-negatif dengan selalu memproses simpul berjarak terkecil dari antrean prioritas.

Tujuan Belajar

·Memahami peran priority queue dalam memilih simpul terdekat
·Menjelaskan proses relaksasi jarak ke tetangga
·Menerapkan Dijkstra untuk menghitung rute tercepat

Cara Kerja

·Set jarak sumber = 0 dan simpul lain = tak hingga
·Ambil simpul dengan jarak sementara terkecil dari priority queue
·Relaksasi tetangga: perbarui jaraknya bila lewat simpul ini lebih pendek
·Tandai simpul sebagai selesai agar tidak diproses ulang
·Ulangi sampai tujuan tercapai atau semua simpul selesai

Prasyarat

·Graf berbobot
·Priority queue (min-heap)

Contoh Nyata

·Google Maps hitung rute tercepat antar persimpangan berdasarkan waktu tempuh
·Aplikasi ojek online cari jalur dengan ongkos jarak paling murah
·Jaringan internet memilih jalur data dengan latency terkecil

Kompleksitas O((V + E) log V) dengan min-heap