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.
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
int i,j;
int Dist_Map[100][100];
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)
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
Sebagai catatan, nilai yang di-copy adalah slot array yang memiliki nilai non-infinite.
- Inisialisasi Bellman-Ford
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
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
Post a Comment