Algoritma Routing

Forward-search algorithm dinyatakan sebagai menentukan jarak terpendek dari node awal yang ditentukan ke setiap node yang ada.Algoritma diungkapkan dalam stage. Dengan k buah stage, jalur terpendek  node k terhadap node sumber ditentukan. Node-node ini ada dalam himpunan N. Pada stage ke (k+1), node yang tidak ada dalam M yang mempunyai jarak terpendek terhadap sumber ditambahkan ke M. Sebagai sebuah node yang ditambahkan dalam M, maka jalur dari sumber menjadi terdefinisi.

Algoritma ini memiliki 3 tahapan :

1.    Tetapkan M={S}. Untuk tiap node nÎN-S, tetapkan C₁(n)=l(S,n).

2.    Cari WÎN-M sehingga C₁(W) minimum dan tambahkan ke M. Kemudian C₁ (n) = MIN[C₁(n), C₁(W) + l(W,n) untuk tiap node nÎN-M. Apabila pada pernyataan terakhir bernilai minimum, jalur dari S ke n sebagai jalur S ke W memotong link dari W ke n.

3.    Ulang langkah 2 sampai M=N.

Keterangan :

N = himpunan node dalam jaringan

S = node sumber

M = himpunan node yang dihasilkan oleh algoritma

l(I,J) = link cost dari node ke I sampi node ke j, biaya bernilai ¥ jika node tidak secara langsung terhubung.

C1(n) : Biaya dari jalur biaya terkecil dari S ke n yang dihasilkan pada saat algoritma dikerjakan.

Tabel berikut ini memperlihatkan hasil algoritma terhadap gambar di muka. Dengan menggunakan S=1.

Tabel Hasil forward search algorithm