Forward Search Algorithm

Forward Search Algorithm
Forward Search Algorithm digunakan untuk menentukan jarak terpendek dari node awal yang ditentukan ke setiap node yang ada. Algoritma diungkapkan dalam stage. Dengan k buah 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 yng mempunyai jarak terpendek terhadap sumber ditambahkan ke M. Sebagai sebuah node yang di tembarvkan dalam M, maka jalur dari sumber menjadi terdefinisi (Gambar 5.4). Algoritma ini memiliki 3 tahapan:

1. Tetapkan M={S). Untuk setiap node neN-S, tetapkan C1(n)=1(S,n).
2. Cari WeN-M sehingga C1(W0 minimum dan tambahkan ke M. Kemudian C1 (n) = MIN[C1(n), C1(W) + 1(W,n) untuk tiap node neN-M. Apabila pernyataan terakhir bernilai minimunv, jalur dari S ke n sebagai jalur S ke W menotong Jink 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
 1 (I,J) = link cost dari node I sampai node ke }, biaya bernilai > jika node tidak secara langsung terhubung.
 C1(n) = biaya daru jalur biaya terkecil dari S ke n yang dihasilkan pada saat algoritma dikerjakan.
Untuk memperjelas dari penggunaan forward search algorithm, perhatikan Gambar.4 yang menjelaskan rute jaringan yang menghubungkan 6 titik (node).