23
2.8.3
Algoritma
Dijkstra
Algoritma
Dijkstra
dipublikasikan
pertama
kali
oleh
E.W.Dijkstra
pada
tahun
1959.
Menurut
Stout
(1997,
p1)
algoritma
Dijkstra
merupakan
pengembangan dari
algoritma
breadth-first
search,
dimana pada algoritma
Dijkstra setiap edge-nya
memiliki
nilai dan selalu bernilai positif.
Perbedaan
yang
lain terletak pada open
list-nya.
Open
list
pada
algoritma
Dijkstra
merupakan
priority
queue,
dimana
vertex
dengan
prioritas
tertinggi
akan
diproses
terlebih
dahulu,
yaitu
vertex
yang
memiliki
nilai
terkecil
pada
open
list.
Jadi
pengaturan priority
queue
pada
Dijkstra
dipengaruhi oleh
nilai
edge
kumulatif dari vertex awal sampai vertex akhir.
Berdasarkan terminologi teori graph, maka suatu jaringan akan terdiri dari suatu
himpunan titik-titik yang disebut node. Node-node tersebut saling dihubungkan oleh
suatu garis dan disebut edge. Beberapa terminologi tambahan dari jaringan ini adalah :
•
Siklus, yaitu lintasan yang diawali pada suatu node dan diakhiri pada node itu juga.
•
Tree,
yaitu suatu jaringan dengan lintasan yang menghubungkan pasangan – pasangan
node, dimana siklus tidak terjadi.
•
Busur maju, yaitu busur yang meninggalkan node.
Gambar 2.10 Busur Maju
•
Busur mundur, yaitu busur yang masuk ke dalam node.
Gambar 2.11 Busur Mundur
 |