Algoritma Bellman Ford

Dalam proses routing (perutean), yang biasa dilakukan adalah menggunakan algoritma untuk menentukan path terpendek dalam tiap-tiap node untuk mendapatkan path secara efisien. Salah satu algoritma yang digunakan adalah algoritma Bellman-Ford.

Key words: algoritma bellman ford adalah shortest path terpendek mudah how to bagaimana routing router mencari tahap tahapan steps tutorial jaringan komputer telekomunikasi logika

Algoritma ini menentukan path terpendek dari seluruh node menuju satu node tertentu. Algoritma Bellman-Ford termasuk jenis perutean State Link, berarti dia hanya berfokus pada arah (next node) dan jarak.

Secara umum, langkah-langkah algoritmanya adalah sebagai berikut:

• Inisialisasi.

Notasi di atas dimaksudkan bahwa untuk setiap nilai jarak D dari node i dimasukkan nilai infinite (tak terdefinisi), dengan semua i tidak sama dengan d. Untuk jarak D dari node d dimasukkan nilai 0.

Perlu diingat bahwa D adalah nilai jarak yang terdapat dalam tabel yang akan dibuat sebagai hasil dari algoritma Bellman-Ford. i menunjukkan node i, sementara d adalah node tujuan (destination).

• Update untuk tiap node i ≠ d.

Dari notasi di atas, dimaksudkan bahwa nilai jarak D dari node i diperbaharui dengan mengecek nilai yang paling kecil di antara penjumlahan nilai jarak C antara node i dan j dengan nilai jarak D dari node j, untuk setiap i yang tidak sama dengan j.

Sebagai catatan, nilai jarak D adalah nilai yang berada pada tabel in-progress, sedangkan nilai jarak C adalah nilai yang berada pada gambar/map node yang diketahui. Node i dianggap sebagai node awal sementara, sementara node j adalah node yang bertetangga dengan node i.

• Ulangi langkah 2 sampai baris iterasi x sama dengan baris iterasi (x-1).

Jika suatu baris pada tabel in-progress telah selesai, maka isinya dibandingkan dengan baris di atasnya. Jika keseluruhannya sudah sama, maka proses dihentikan. Jika ternyata ada yang berbeda (terdapat nilai jarak D dari node i yang berubah nilai), maka langkah ke-2 diulangi kembali, yaitu meng-update nilai jarak Di-nya kembali.

Untuk mempermudah pemahaman, mari lakukan contoh menggunakan gambar node seperti ini.

Mari kita mencoba mencari path terpendek menuju node 3.

Sesuai langkah algoritma, mari kita definisikan terlebih dahulu seluruh Di sebagai infinite. Agar mempermudah pekerjaan, mari dibuat sebuah tabel sebagai berikut:

Sebagai catatan, notasi pada tabel in-progress mengikuti format (n,D), dengan n adalah next node dari node i, sementara D adalah total jarak dari node i ke node d. Next node -1 dimaksudkan bahwa node i belum mengetahui cara menuju node d karena masih berupa inisialisasi.

Tahap selanjutnya adalah meng-update Di. Kita mulai dari D-1

Node 1, berarti i = 1. Node 1 hanya memiliki tetangga node 2, berarti j = 2.

Sehingga kita bisa mengetahui nilai Temp = Cij + Dj = C12 + D2 = 2 + ∞ = ∞.

Karena nilainya masih infinite, maka nilainya tidak berubah. (D-1 masih tertulis (-1,∞))

Selanjutnya adalah D-2.

Node 2, berarti i = 2. Node 2 memiliki tetangga node 1, node 3, dan node 4. (Dari sini sebenarnya kita bisa secara langsung mengetahui bahwa node akan langsung membuat path menuju node 3, namun lebih baik kita memakai algoritma dasarnya sehingga lebih mengerti.)

Sehingga kita melakukan perbandingan dari beberapa perhitungan berikut:

- Cij + Dj = C21 + D1 = 2 + ∞ = ∞

- Cij + Dj = C23 + D3 = 3 + 0 = 3

- Cij + Dj = C24 + D4 = 1 + ∞ = ∞

Dari hasil tersebut, maka bisa dipastikan bahwa nilai minimumnya adalah 3 dengan next node 3, sehingga kolom D-2 berubah menjadi (3,3).

Selanjutnya dilakukan kepada semua Di sehingga akan dihasilkan tabel sebagai berikut untuk interasi ke-1:

Dari sini bisa disimpulkan bahwa pada iterasi ke-1, kolom Di yang akan berubah adalah node yang secara langsung terhubung dengan node d.

Untuk iterasi ke-2, akan dihasilkan tabel sebagai berikut:

Beberapa perubahan yang terjadi dalam node tersebut:

Pada Node 1, kita ulangi penghitungan path terpendeknya.

(i = 1, j = 2)

Cij + Dj = C12 + D2 = 2 + 3 = 5.

Bisa dilihat bahwa nilainya sekarang berubah. Hal ini dikarenakan nilai D2 setelah iterasi 1 sudah memiliki nilai, yaitu 3. Inilah yang membedakan nilai jarak C dan nilai jarak D. Nilai jarak C tidak akan berubah, sementara nilai jarak D dapat saja berubah. Hal itu juga yang terjadi untuk D-4

Node 4 memiliki tetangga node 2, node 3, node 5, dan node 7.

(i = 4 dan j = 2 / 3 / 5 / 7)

Dibandingkan yang memiliki nilai terrendah:

- Cij + Dj = C42 + D2 = 1 + 3 = 4

- Cij + Dj = C43 + D3 = 7 + 0 = 7

- Cij + Dj = C45 + D5 = 4 + 3 = 7

- Cij + Dj = C47 + D7 = 5 + ∞ = ∞

Dari hasil di atas, ternyata node 4 bisa menuju node 3 dengan jarak lebih kecil melalui node 2, bukan langsung menuju node 3. Sehingga, kolom D-4 berubah menjadi (2,4).

Secara singkat, tabel hasilnya akan berisi sebagai berikut:

Kiranya ilmu yang sedikit ini bisa membantu saudara. Jika ada yang ingin ditanyakan, jangan segan-segan untuk meninggalkan comment ya.

Terima kasih banyak...!