DIJKSTRA'S ALGORITHM

Dijkstra’s Algorithm

Dokumen ini membahas algoritma Dijkstra, sebuah metode yang efisien untuk menemukan jalur terpendek dari satu simpul sumber ke semua simpul lainnya dalam graf berbobot positif.

---

1. Apa Itu Dijkstra’s Algorithm?

Dijkstra’s Algorithm adalah algoritma untuk mencari jarak terpendek dalam graf berbobot non-negatif. Algoritma ini digunakan untuk menemukan jalur paling efisien antara dua simpul atau dari satu simpul ke semua simpul lainnya dalam graf.

---

2. Cara Kerja Algoritma Dijkstra

Langkah-langkah algoritma:

1. Inisialisasi jarak semua simpul dengan nilai tak hingga (∞), kecuali simpul awal yang diberi nilai 0.
2. Pilih simpul yang memiliki jarak minimum dan belum diproses.
3. Periksa semua tetangga dari simpul tersebut. Jika jarak melalui simpul ini lebih kecil dari jarak yang tercatat, perbarui nilai jarak tersebut.
4. Tandai simpul sebagai telah diproses.
5. Ulangi langkah 2–4 hingga semua simpul telah diproses atau simpul tujuan ditemukan.

---

3. Contoh Kasus

Graf sebagai berikut:

A --1--> B --2--> D --1--> F
|       |
5       1
v       v
C       E --2--> F
 \-----2---->/

Tujuan: Menentukan jalur terpendek dari simpul A ke simpul F.

Proses:

• Dari A: Jarak awal = 0.
• Jarak ke B = 1, ke C = 5
• Dari B, perbarui jarak ke C (1+2=3), ke D (1+2=3), ke E (1+1=2)
• Dari E, jarak ke F = 2+2 = 4

Dua jalur ditemukan dengan total jarak 4:

• A → B → E → F
• A → B → D → F

---

4. Aplikasi Nyata

• Navigasi dan Transportasi: Digunakan pada aplikasi peta digital untuk menghitung rute tercepat.
• Pengiriman dan Logistik: Menentukan rute optimal untuk distribusi barang.
• Jaringan Komputer: Menentukan jalur transmisi data paling efisien.

---

5. Kelebihan

• Menjamin hasil jalur terpendek dengan asumsi bobot positif.
• Dapat digunakan untuk mencari jarak minimum dari satu simpul ke semua simpul lainnya.
• Implementasi stabil dan digunakan luas.

---

6. Kekurangan

• Tidak dapat digunakan jika graf mengandung bobot negatif.
• Kurang efisien pada graf besar yang jarang terhubung.
• Menghitung semua jalur, walaupun hanya satu simpul tujuan yang dibutuhkan.

---

7. Kesimpulan

Algoritma Dijkstra adalah metode yang andal dan efisien untuk menyelesaikan masalah jalur terpendek dalam graf berbobot positif. Dengan sifatnya yang deterministik dan optimal, algoritma ini sangat berguna dalam berbagai skenario praktis.