Algoritma Routing

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.

Backward search algorithm

Menentukan jalur biaya terkecil yang diberikan node tujuan dari semua node yang ada. Algoritma ini juga diproses tiap stage. Pada tiap stage, algoritma menunjuk masing-masing node.

Definisi yang digunakan :

N = Himpunan node yang terdapat pada jaringan

D= node tujuan

l(i,j) = seperti keterangan di muka

C₂(n) = biaya dari jalur biaya terkecil dari n ke D yang dihasilkan saat algoritma dikerjakan.

Algoritma ini juga  terdiri dari 3 tahapan :

1.     Tetapkan C₂(D)=0. Untuk tiap node nÎN-D, tetapkan C₂(n) =¥.

2.     Untuk tiap node nÎN-D, tetapkan C₂(n)=MIN WÎN[C₂(n), C₂(W) + l(n,W)]. Apabila pada pernyataan terakhir bernilai minimum, maka jalur dari n ke D saat ini merupakan link dari n ke W dan menggantikan jalur dari W ke D

3.     Ulangi langkah ke –2 sampai tidak ada cost yang berubah.

e='mso-ansi-language:SV'>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.