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.

Tabel berikut adalah hasil pengolahan gambar 1 dengan D=1

Tabel Hasil backward search algorithm