39
2.10
Algoritma Dijkstra
Menurut Wiitala
(1987, p240), Algoritma Dijkstra pertama kali
ditemukan
oleh
E.
Dijkstra
pada
tahun
1959,
dan
merepresentasikan sebuah
shorthpath.
Ide
dibalik
algoritma
Dijkstra
ini
cukup
pintar.
Algoritma
ini
membuat dua
track
yang
berisi
verteks,
yang
satu
berisi
verteks
yang
memiliki
path terpendek dari verteks awal /
verteks
yang diberikan, dan track ke dua berisi
sisa
verteks yang
lainnya.
Saat
algoritma dimulai,
track
pertama hanya
berisi
verteks
awal,
kemudian
dengan
proses
iterasi
dalam
algoritma,
sebuah
verteks
dari
track
kedua
dihapus dan
dimasukkan
ke
dalam
track
pertama. Begitu
seterusnya
hingga
verteks
akhir
yang
diharapkan
masuk
ke
dalam
track
kedua
maka proses berhenti.
2.10.1 Cara Kerja Algoritma Dijkstra
Algoritma
Dijkstra
merupakan
algoritma
untuk
menemukan path
terpendek
dari
verteks
awal
s,
ke
semua
verteks
dalam
graph
(V-1).
V
adalah
semua
verteks
yang
terdapat dalam
graph.
Algoritma Dijkstra
membagi verteks-verteks
yang pernah ditelusuri
menjadi S
dan F. S
terdiri
dari
verteks-verteks yang
telah
didapatkan
jalur
terpendeknya,
sedangkan
F
terdiri
dari
verteks-verteks
yang
path
terpendeknya
belum
ditemukan.
Verteks-verteks yang
tidak
termasuk
S
dan
F
adalah
verteks
yang belum pernah ditelusuri (V –( S + F )).
Algoritma Dijkstra
terus
meng–update
d,
yang
berisi
jarak
terpendek
yang
terbaru
dari
s
ke
masing-masing verteks.
Jika
sebuah
verteks
v
termasuk
dalam
S,
maka
d[v]
sudah
pasti
merupakan
jarak
 |