Algoritma Bellman-Ford dan Dijkstra adalah dua metode yang umum digunakan dalam routing untuk menentukan jalur terpendek dari satu titik ke titik lainnya dalam graf berbobot. Berikut adalah penjelasan tentang cara kerja masing-masing algoritma:
1. Algoritma Bellman-Ford
- Pendekatan: Algoritma ini memanfaatkan metode iteratif untuk memperbarui jarak terpendek dari titik awal ke semua simpul di dalam graf.
- Langkah Kerja:
- Inisialisasi jarak dari titik awal ke semua simpul dengan nilai tak terhingga (infinity), kecuali jarak ke titik awal itu sendiri yang di-set menjadi 0.
- Untuk setiap simpul dalam graf, lakukan iterasi sebanyak (jumlah simpul – 1) kali:
- Untuk setiap edge (sisi) dalam graf, periksa apakah jarak ke simpul tujuan dapat diperbarui dengan menjumlahkan jarak ke simpul asal dengan bobot edge. Jika bisa, perbarui jarak tersebut.
- Setelah iterasi, lakukan pemeriksaan untuk mendeteksi siklus negatif dengan memeriksa kembali semua edge. Jika jarak dapat lagi diperbarui, berarti ada siklus negatif.
- Kelebihan: Dapat menangani graf yang memiliki bobot negatif, selama tidak ada siklus negatif yang dapat diakses dari titik awal,.
2. Algoritma Dijkstra
- Pendekatan: Algoritma ini menggunakan metode greedy yang memilih simpul terdekat yang belum dikunjungi dan memperbarui jarak ke tetangganya.
- Langkah Kerja:
- Inisialisasi jarak dari titik awal ke semua simpul dengan nilai tak terhingga, kecuali jarak ke titik awal yang di-set 0. Jaga agar ada daftar atau struktur data untuk tracking simpul yang sudah dikunjungi.
- Pilih simpul dengan jarak terpendek (minimal) dari daftar. Tandai simpul ini sebagai sudah dikunjungi.
- Untuk setiap tetangga dari simpul yang baru saja dikunjungi, periksa apakah jarak baru (jarak ke simpul saat ini ditambah bobot edge ke tetangga) lebih kecil dibandingkan jarak yang terdaftar saat ini. Jika lebih kecil, perbarui jarak tersebut.
- Ulangi langkah 2 dan 3 hingga semua simpul telah dikunjungi, atau tidak ada simpul yang dapat dijangkau.
- Kelebihan: Lebih efisien dalam hal waktu komputasi pada graf dengan bobot non-negatif dibandingkan dengan Bellman-Ford, karena tidak perlu mengecek siklus negatif dan memberi hasil lebih cepat dalam banyak kasus,.
Kesimpulan
Kedua algoritma ini memiliki kelebihan dan kekurangan masing-masing dalam konteks routing. Di mana Algoritma Dijkstra lebih unggul dalam efisiensi waktu, Algoritma Bellman-Ford lebih fleksibel dalam menangani graf dengan bobot negatif,.
Refernsi : https://ejournal.upm.ac.id/index.php/energy/article/download/113/451