46
b. Memilih jalur tersingkat dari Slipi ke Pasar Minggu
2.9.3
Definisi Algoritma Dijkstra
Algoritma Dijkstra ditemukan pertama kali oleh, Edsger Dijkstra.
Algoritma
ini adalah
sebuah greedy algorithm
dalam memecahkan permasalahan
jarak terpendek untuk sebuah
graf berarah
(directed
graph)
dengan
bobot-bobot
sisi yang bernilai tidak-negatif (id.wikipedia.org).
2.9.4
Penerapan Penggunaan Algoritma Dijkstra
Algoritma
Djikstra
melakukan komputasi
pencarian
rute
terpendek
antara
simpul
sumber
dan
simpul
tujuan
berdasarkan bobot
pada
sisi
yang
menghubungkan simpul-simpul
dalam
graph.
Bobot
pada
sisi
bisa
berarti
jarak.waktu ataupun
bobot
lainnya.
Jalur
terpendek
dalam
graph
adalah
jumlah
total
minimum
bobot
dari
sisi-sisi
yang
menghubungkan simpul
sumber
dengan
simpul
tujuan.
Algoritma
Djikstra
adalah
algoritma
pencarian jalur
terpendek
klasik
yang
dapat
ditemukan pada
banyak
literatur
seperti
pada
referensi.
Algoritma
Djikstra
bekerja dengan cara
mengunjungi
simpul-simpul pada
graph
dimulai
dengan
simpul
sumber.
Algoritma
Djikstra
kemudian secara
berulang
memilih
simpul-simpul terdekat
dan
menghitung
total
bobot
semua
sisi
yang
dilewati
untuk
mencapai
simpul
tersebut.
Pada
algoritma
djikstra
total
biaya
untuk mencapai suatu simpul dihitung dengan :
 |