35
Cost
dari
shortest
path
dapat
dihitung
dari
total
nilai
minimum
yang
ada
pada
edge-nya.
Dalam
mencari
shortest
path,
hasil
didapatkan
setelah
melewati
node
–
node
tertentu, sampai
akhirnya tujuan
akhir
node
dapat
dicapai.
Untuk
itu,
pencarian
bukan
hanya
dilakukan
dengan
1
alternatif,
namun
bisa
ada
kalanya
shortest
path
tersebut
baru
dapat
ditemukan
setelah
membandingkan
beberapa
alternatif untuk mencapai tujuan
2.5.2.2 Single Source Shortest Path
Menurut
Horowitz (1998,
p241),
single
source
shortest
path adalah jarak
terpendek dari setiap
verteks
tunggal pada graph
berarah
yang berbobot
menuju
verteks
tujuan
tertentu.
Disebut
single
source
karena
membutuhkan satu
titik
sebagai awal pencarian.
Algoritma
yang termasuk single
source
shortest
path
ini
adalah Algoritma Dijkstra dan Bellman Ford.
2.5.2.3 Algoritma Dijkstra
Algoritma
Dijkstra
digunakan
untuk
menemukan
path
bernilai
terkecil
dari
verteks awal tunggal ke semua
verteks pada graph.
Algoritma
ini ditemukan
oleh
Edsgar
Wybe
Dijkstra
(Horowitz et
al,
1998,
p243).
Algoritma
ini
akan
melihat
verteks
yang
terdeteksi dengan
verteks awal,
melihat successor
dari
verteks tersebut kemudian
memperbarui
jaraknya dari awal, demikian seterusnya
sampai verteks tujuan berhasil ditemukan. Hasilnya pasti berupa jalur
terpendek.
 |