Algoritma Dijkstra — Jalur Terpendek Langkah demi Langkah

Algoritma Dijkstra mencari jalur terpendek dari satu simpul awal dalam graf berbobot, selama setiap bobot sisi bernilai nonnegatif. Jika Anda hanya peduli pada satu tujuan, Anda bisa berhenti begitu tujuan itu diselesaikan.

Langkah intinya bersifat greedy: selalu lanjut dari simpul yang belum diselesaikan dengan jarak diketahui paling kecil. Ini hanya bekerja dalam kondisi bobot nonnegatif.

Apa yang Diselesaikan oleh Algoritma Dijkstra

Gunakan algoritma Dijkstra ketika Anda memiliki graf dengan biaya pada sisi-sisinya dan ingin mencari rute termurah. Biaya itu bisa merepresentasikan jarak, waktu tempuh, energi, atau besaran lain yang ingin Anda minimalkan.

Algoritma ini bekerja pada graf berarah maupun tak berarah. Syarat utamanya jelas: setiap bobot sisi harus setidaknya $0$.

Cara Kerja Algoritma

Setiap simpul menyimpan jarak tentatif dari simpul awal. Pada awalnya, simpul awal memiliki jarak $0$ dan setiap simpul lain memiliki jarak $\infty$.

Lalu ulangi loop ini:

1. Pilih simpul yang belum diselesaikan dengan jarak tentatif paling kecil.
2. Periksa setiap tetangga melalui simpul itu.
3. Jika rute baru lebih murah, perbarui jarak tetangga tersebut.
4. Tandai simpul saat ini sebagai selesai.

Langkah 3 disebut relaksasi. Simpul yang sudah diselesaikan berarti selesai: jarak terpendeknya sudah final, asalkan graf tidak memiliki bobot sisi negatif.

Algoritma Dijkstra Langkah demi Langkah

Berikut prosedur lengkapnya dalam bentuk ringkas:

1. Pilih simpul awal.
2. Tetapkan jaraknya menjadi $0$ dan setiap jarak lain menjadi $\infty$.
3. Pilih simpul yang belum diselesaikan dengan jarak tentatif paling kecil.
4. Lakukan relaksasi pada sisi keluar dari simpul itu.
5. Tandai simpul itu sebagai selesai.
6. Ulangi sampai semua simpul yang dapat dijangkau selesai, atau berhenti setelah simpul target Anda diselesaikan.

Jika Anda juga menyimpan simpul sebelumnya yang menyebabkan setiap pembaruan, Anda bisa mendapatkan kembali jalur sebenarnya, bukan hanya jarak akhirnya.

Contoh Jalur Terpendek yang Dikerjakan

Misalkan graf memiliki bobot sisi berikut:

• $A \to B = 4$
• $A \to C = 1$
• $C \to B = 2$
• $B \to D = 1$
• $C \to D = 5$

Kita ingin mencari jalur terpendek dari $A$ ke $D$.

Mulai dengan:

$$\text{dist}(A)=0,\quad \text{dist}(B)=\infty,\quad \text{dist}(C)=\infty,\quad \text{dist}(D)=\infty$$

Selesaikan $A$ terlebih dahulu dan lakukan relaksasi pada sisi-sisinya:

$$\text{dist}(B)=4,\quad \text{dist}(C)=1$$

Jarak terkecil yang belum diselesaikan sekarang ada pada $C$, jadi selesaikan $C$ berikutnya.

Jika melalui $C$:

• Melalui $C$, jalur ke $B$ berbiaya $1+2=3$, yang lebih baik daripada $4$, jadi perbarui $\text{dist}(B)=3$.
• Melalui $C$, jalur ke $D$ berbiaya $1+5=6$, jadi tetapkan $\text{dist}(D)=6$.

Sekarang $B$ memiliki jarak terkecil yang belum diselesaikan, jadi selesaikan $B$.

Jika melalui $B$, biaya jalur ke $D$ adalah:

$$3+1=4$$

Itu lebih baik daripada $6$, jadi perbarui $\text{dist}(D)$ dari $6$ menjadi $4$.

Sekarang $D$ adalah simpul terkecil yang belum diselesaikan. Selesaikan simpul itu, lalu berhenti.

Jalur terpendeknya adalah:

$$A \to C \to B \to D$$

dengan total biaya:

$$1+2+1=4$$

Contoh ini menunjukkan pola pentingnya: rute yang awalnya tampak lebih buruk, $A \to B$, kemudian menjadi lebih baik melalui $C$. Algoritma Dijkstra mengizinkan hal itu selama $B$ masih belum diselesaikan. Setelah sebuah simpul diselesaikan, jaraknya tidak akan berubah.

Mengapa Bobot Nonnegatif Penting

Misalkan simpul termurah saat ini yang belum diselesaikan memiliki jarak $d$. Setiap jalur baru ke simpul itu yang ditemukan nanti harus datang dari simpul lain yang belum diselesaikan dengan jarak tentatif setidaknya $d$, lalu menambahkan sisi dengan bobot setidaknya $0$.

Jadi rute yang ditemukan belakangan itu tidak mungkin mengalahkan $d$. Itulah sebabnya menyelesaikan jarak tentatif terkecil aman ketika semua bobot bernilai nonnegatif.

Jika ada sisi negatif, argumen itu runtuh. Jalur yang sekarang tampak mahal bisa menjadi lebih murah nanti, yang berarti menyelesaikan simpul terlalu cepat dapat memberi jawaban yang salah.

Kesalahan Umum dalam Algoritma Dijkstra

Menggunakannya pada sisi negatif

Bahkan satu sisi negatif saja bisa merusak logika greedy. Jika bobot negatif mungkin muncul, gunakan metode jalur terpendek yang lain.

Menganggap "sudah terlihat" sebagai "sudah selesai"

Sebuah simpul bisa saja sudah memiliki jarak tentatif tetapi masih belum selesai. Hanya simpul yang sudah diselesaikan yang memiliki jarak terpendek final.

Lupa tabel simpul sebelumnya

Jarak memberi tahu biayanya. Jika Anda juga ingin rutenya, simpan simpul mana yang terakhir kali memperbaiki setiap jarak.

Di Mana Algoritma Dijkstra Digunakan

Algoritma Dijkstra digunakan ketika suatu masalah dapat dimodelkan sebagai pergerakan melalui graf dengan biaya nonnegatif:

• Perencanaan rute pada peta
• Routing jaringan
• Pergerakan robot pada grid berbobot
• Pathfinding dalam game ketika biaya gerak bervariasi

Algoritma ini juga merupakan contoh standar dari algoritma greedy yang kebenarannya bergantung pada syarat yang tepat.

Coba Soal Serupa

Gambarlah sebuah graf dengan lima simpul dan bobot sisi positif, lalu jalankan algoritma Dijkstra secara manual dengan tabel jarak. Jika Anda ingin langkah berikutnya yang bagus, coba versi Anda sendiri pada graf baru dan periksa tepat kapan setiap simpul menjadi aman untuk diselesaikan.