Algoritma Dijkstra ditemukan oleh Edsger W. Dijkstra pada tahun 1956 dan dipublikasikan pada tahun 1959 dalam makalah berjudul:
"A Note on Two Problems in Connexion with Graphs"
Dijkstra adalah salah satu tokoh paling berpengaruh dalam ilmu komputer. Selain algoritma shortest path, ia juga dikenal karena kontribusinya pada:
- Pemrograman terstruktur (Structured Programming)
- Sistem operasi
- Sinkronisasi proses
- Semaphore
- Teori graf
Latar Belakang Penemuan
Pada tahun 1956, Dijkstra bekerja di pusat penelitian matematika Belanda (Mathematisch Centrum) dan diminta untuk menyelesaikan masalah:
"Bagaimana menentukan rute terpendek dari satu kota ke kota lain?"
Saat itu komputer masih sangat terbatas. Dijkstra kemudian merancang algoritma yang sederhana namun efisien untuk mencari jalur terpendek pada graf berbobot positif.
Menurut cerita yang sering dikutip, algoritma tersebut dirancang hanya dalam waktu sekitar 20 menit sambil menikmati secangkir kopi di Amsterdam.
2. Apa itu Algoritma Dijkstra?
Algoritma Dijkstra adalah algoritma Greedy yang digunakan untuk mencari:
- Jalur terpendek dari satu titik sumber (single source)
- Ke seluruh simpul lain dalam graf
Algoritma ini bekerja pada:
✅ Graph berbobot (weighted graph)
✅ Bobot bernilai positif
❌ Tidak cocok untuk bobot negatif
3. Konsep Dasar
Misalkan terdapat graph berikut:
4
A ------ B
| |
2 | | 1
| |
C ------ D
3
Tujuan:
Mencari jalur terpendek dari A ke semua node.
Referensi
Latihan
Sebuah perusahaan layanan Food Delivery ingin meningkatkan kecepatan pengiriman makanan kepada pelanggan. Saat ini pengemudi sering memilih rute berdasarkan perkiraan pribadi sehingga waktu pengiriman menjadi tidak optimal.
Untuk mengatasi masalah tersebut, perusahaan ingin membangun sistem yang dapat menentukan rute tercepat dari restoran ke lokasi pelanggan menggunakan Algoritma Dijkstra.
Pengumpulan Tugas
Form Monitoring Tugas
Absensi
No comments:
Post a Comment