Algoritma Dijkstra, dinamai menurut penemunya, Edsger Dijkstra, adalah sebuah algoritma rakus
(greedy algorithm) dalam memecahkan permasalahan jarak terpendek (shortest path problem) untuk sebuah graf berarah (directed graph) dengan bobot-bobot sisi (edge weights) yang bernilai tak-negatif.
Misalnya, bila vertices dari sebuah graf melambangkan kota-kota dan bobot sisi (edge weights)
melambangkan jarak antara kota-kota tersebut, maka algoritma Dijkstra
dapat digunakan untuk menemukan jarak terpendek antara dua kota.
Input algoritma ini adalah sebuah graf berarah yang berbobot (weighted directed graph) G dan sebuah sumber vertex s dalam G dan V adalah himpunan semua vertices dalam graph G.
Setiap sisi dari graf ini adalah pasangan vertices (u,v) yang melambangkan hubungan dari vertex u ke vertex v.
Cara Kerja dari Algoritma Dijkstra dapat diterapkan pada ilmu jaringan komputer. Jaringan
komputer dapat dimodelkan sebagai sebuah graf, dengan setiap simpul menyatakan sebuah
komputer/router dan sisi didalam graf menyatakan saluran komunikasi(sering disebut
link). Setiap sisi mempunyai label nilai( yang disebut bobot). Bobot tersebut dapat
menyatakan jarak geografis(dalam km), kecepatan transfer data, waktu pengiriman).
Mencari
lintasan terpendek dari router asal kerouter tujuan dapat diartikan sebagai menentukan lintasan
terpendek dari simpul asal kesimpul tujuan didalam graf yang merepresentasikan jaringan
komputer tersebut. Algoritma Dijkstra adalah algoritma yang banyak digunakan untuk
mencari lintasan terpendek.
Kegunaan dari Algoritma Dijkstra
Dapat dijelaskan sebagai berikut. Misalkan, sebuah simpul
sumber s di sebuah jaringan, ingin memperoleh jarak yang tersingkat dan
termurah ke simpul lainnya yang ada dijaringan tersebut, misalnya ke simpul i. Label
jarak : d(l) menunjukkan jarak antara simpul s dan simpul i. Setiap langkah
dalam pencarian jalan tersebut ("antara'), simpul-simpul ini kelompokkan
kedalam dua jenis simpul, yaitu .. simpul dengan label jarak permanen dan
simpul dengan label jarak sementara. Label jarak permanen merupakan jarak
terdekat dari simpul s ke simpul i. Label jarak sementara merupakan batas atas
jarak s ke 1 pada 'alan denganjarak tersingkat.
Selain
itu ada inforrnasi tentang sebuah simpul antara yang dilalui sebelumnya
("predecessor"). Langkah-langkah pencarian jalan tersingkat dan
termurah tersebut adalah sebagai berikut :
Labelkan
d(s) = 0 sebagai label jarak permanen, dan d(i) = x sebagai label jarak
sementara, untuk simpul lainnya selain simpul s.
Setiap
langkah iterasi : label jarak d(i) merupakan jarak terdekat dari simpul s
sepanjang jaln yang label-label nodenya merupakan label jarak perrnanen.
Algoritmanya
. memilih simpul i dengan label jarak sementara minimim dan membuatnya menjadi
permanen, dan diteruskan dengan memeriksa link-link yang kcluar dari i untuk
memperbaharul label jarak dari simpul yang berdekatan (terhubung ke simpul
tersebut). Pemeriksaan jarak-jarak tersebut dilakukan dengan: Bila d(j) >
D(i) + Cij = B, maka dibuat d(j) = B sebagai harga label yang baru dari d(J).
4). Langkah berhenti bila semua label sudah merupakan label permanen. Dalam
label dicantumkan simpul processor.
kami juga mempunyai artikel mengenai algoritmaa djikstra, bisa dibaca di
BalasHapushttp://repository.gunadarma.ac.id%2Fbitstream%2F123456789%2F2734%2F1%2FKommit2000_komputasi_008.pdf&ei=452TUN6IC5GHrAfq3ICQBA&usg=AFQjCNFjUuLg5YEIWyE4wM0RKhtEMqWHEw&sig2=ZbmirwkkaJyvPx1woPKTqg
semoga bermanfaat :D