47
for i from 1 to n
for j from 1 to n
if jarak[i,j] >
jarak[i,k] + jarak[k,j] jarak[i,j] = jarak[i,k] +
jarak[k,j]
sebelum[i,j] = sebelum[k,j]
return jarak
}
Algoritma ini berjalan dengan waktu O(V3).
2.13
Pencarian jalur dengan Breadth-first search dan Depth-first order
Kedua
metode
ini
sering
digunakan dalam
mencari
solusi
dari
suatu
permasalahan. Pencarian
suatu
solusi
yang
optimal
dapat
dilihat
dari
4
kategori
umum yaitu Completeness, Time Complexity, Space Complexity dan Optimalty.
¾
Breadth First Search
Pencarian dilakukan pada
semua
node
dalam
setiap
level
secara
berurutan
dari
kiri
kekanan.
Jika
pada
satu
level
belum
ditemukan solusi,
maka
pencarian
dilanjutkan pada
level
berikutnya.
Demikia
n
seterusnya
sampai
ditemukan solusi.
Dengan
strategi
ini,
maka
dapat
dijamin
bahwa
solusi
yang ditemukan adalah
yang paling baik
(
Optimal). Tetapi
BFS
harus
menyimpan
semua
node
yang
pernah
dibangkitkan. Hal
ini
harus
dilakukan
untuk penelusuran balik jika solusi sudah ditemukan.
¾
Depth-First Order
Pencarian dilakukan pada
satu
node dalam
setiap
level dari
yang paling
kiri. Jika pada level yang paling dalam, solusi belum ditemukan, maka
 |