Algoritma Dijkstra

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.