Algoritma Bellman-Ford: Implementasi dalam Program dengan Bahasa C

Singkat cerita, saya diberikan tugas dari mata kuliah "Jaringan Komputer" untuk membuat sebuah program yang dapat mengoperasikan algoritma bellman-ford dan membuat keluaran berupa tabel jalur terpendek masing-masing node seperti yang sudah dijelaskan disini. Ditambah lagi, saya diminta agar program ini dapat membaca sebuah file txt sebagai data inputan. Untungnya Beliau tidak menyebutkan bahwa hasil keluarannya harus berupa file txt pula karena saya masih pemula dalam pemrograman bahasa C.

Keywords: program bellman ford algoritma bahasa c tutorial baca file parsing txt input output source code jaringan komputer router routing

Di sini saya akan menjabarkan beberapa poin penting dalam struktur program yang saya buat. Saya menampilkan source code dalam bentuk gambar karena jika saya tuliskan di isi blog nanti akan bertabrakan dengan HTML blog jadi lewat gambar aja ya biar aman.

• Inisialisasi Array

Disini kita akan membuat sebuah array yang mendata seluruh jarak antar router yang tersedia. Pada awalnya, dianggap bahwa seluruh node tidak tersambung, sehingga inisialisasinya adalah sebagai berikut.

int i,j;
int Dist_Map[100][100];

Bagian di atas menunjukkan bahwa array Dist_Map berbentuk 2 dimensi dengan ukuran 100 x 100 slot data. Untuk setiap slot data tersebut, diisikan nilai 9999 sebagai anggapan infinite atau tak terdefinisi. Hal ini dimaksudkan bahwa untuk setiap node tidak saling terhubung. Nilai antar node baru dimasukkan saat pembacaan file input.

• Proses baca file txt sebagai input (parsing)

FILE *infile;

char line[4950];

int p,q,Temp;

int MaxNode;

Dari inisialisasi di atas, infile adalah pointer file. infile kemudian digunakan untuk membuka file bernama "input.txt" (lebih baik diletakkan di folder yang sama dengan program) dengan operasi "r" (read). Perlu terdapat mekanisme error (if(!infile)) sehingga jika tidak ada file input.txt pada folder yang sama, maka akan muncul pesan peringatan dan program akan berhenti (return 1).

Untuk mulai pembacaannya, digunakan array line dan operasi fgets sebagai pengecekan bahwa file pada pointer infile masih ada isinya.

Dengan operasi fscanf, akan dibaca format dalam file tersebut Rp Rq. Contohnya jika R1 R2 maka p=1 dan q=2. Setelah itu ditentukan antara nilai p atau q yang paling besar yang kemudian dimasukkan sebagai nilai MaxNode. Karena nanti akan dimasukkan sebagai index array Dist_Map, nilai p dan q diturunkan 1. Kemudian dibaca isi file berikutnya untuk dimasukkan ke variabel Temp dan selanjutnya dimasukkan ke array Dist_Map dengan index p dan q.

Oh iya... entah kenapa dari file input.txt baris pertamanya tidak bisa dibaca, jadi isi-isi file seperti R1 R2 3 lebih baik diletakkan mulai baris kedua.

• Diperhatikan nilai antar node

Perlu diperhatikan bahwa jika node-node tersusun dengan undirected graph (edge tak berarah), maka jarak node a ke b adalah sama dengan b ke a. Sehingga perlu ada fungsi untuk memasukkan nilai array tersebut.

Sebagai catatan, nilai yang di-copy adalah slot array yang memiliki nilai non-infinite.

• Inisialisasi Bellman-Ford

Seperti yang sudah dibahas sebelumnya, Bellman-Ford diinisialisasi dengan notasi sebagai berikut.

Jika diimplementasi dalam program, saya membuatnya seperti ini.

Array Dist_Table berfungsi untuk menyimpan nilai jarak pada tabel, sementara array Next_Node berfungsi untuk menyimpan node berikutnya. Hal ini untuk mengikuti format penulisan tabel hasil algoritma yang memiliki format (n,D). Label Old untuk baris x, sementara label New untuk baris x+1 karena nanti akan dipakai untuk perbandingan isi tabel sebagai sentinel loop.

• Operasi Bellman-Ford

Notasi yang diketahui:

Dalam program:

Ini dimaksudkan bahwa TempResult akan berisi hasil penjumlahan antara setiap jarak node i-j yang sebenarnya (Cij)(Dist_Map) dengan nilai tabel sebelumnya (Dj)(Dist_Table_Old) yang kemudian akan dibandingkan mana yang lebih kecil antara TempResult dengan Dist_Table_New. Sehingga diinginkan akhir loop nanti akan menghasilkan Dist_Table_New yang paling kecil yang bisa didapat. Next_Node_New juga akan berisi nilai j sebagai next node yang menyediakan path tersingkat.

• Comparing Baris Tabel

Perbandingan nilai tabel baris x dengan baris x+1 perlu dilakukan agar operasi pada satu tabel berhenti dilakukan karena perhitungan algoritma Bellman-Ford pada suatu tabel akan berhenti jika nilai pada satu baris telah sama dengan nilai pada baris sebelumnya.

Oh iya... sentinel-nya adalah jml_benar < (MaxNode-1) karena dalam satu tabel ada MaxNode-1 kolom.

Itu saja yang bisa saya bagi kepada para pembaca. Jika mungkin ada yang salah, silahkan isikan di comment di bawah ini. Terima kasih.

[EDIT 20/09/2013]
Berikut saya lampirkan link untuk program penuhnya. Semoga bermanfaat.
http://www.4shared.com/rar/3KHkfklN/Jarkom_bellman-ford_v1.html
[09-Mar-15] Added Mega download link.
https://mega.co.nz/#!lRpQ2TbT!le8GatwkA4T8caQUdcGxyOjebqTIMNIPDl1hAYENc_0