GraphsMenengahFase D–FE1E5

DIJKSTRA 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.

Example use case

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

Syllabus

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

Objectives

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

How It Works

·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

Prerequisites

·Graf berbobot
·Priority queue (min-heap)

Real-World Uses

·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

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