Algoritma Dijkstra (Review) Dan Implentasinya
Menurut Artikel yang terdapat pada posting di Wikipedia tentang Algoritma Dijkstra, Algoritma Dijkstra adalah Sebuah Algoritma Rakus (Greedy) yang dipakai untuk untuk memecahkan permasalahan dalam pencarian terpendek untuk sebuah gaph berarah dengan bobot-bobot sisi yang bernilai tak negatif. Algoritma Dijkstra di temukan oleh seorang ilmuan komputer yang bernama Edsger Dijkstra.
Animasi Dijkstra |
Algoritma Dijkstra merupakan salah satu algoritma yang efektif dalam memberikan lintasan terpendek dari suatu lokasi ke lokasi yang lain. Prinsip dari algoritma Dijkstra dengan pencarian dua lintasan yang mempunyai bobot paling kecil. Algoritma Dijkstra memiliki iterasi untuk mencari titik yang jaraknya dari titik awal adalah paling pendek. Pada setiap iterasi, jarak titik yang diketahui (dari titik awal) diperbarui bila ternyata didapat titik yang baru yang memberikan jarak terpendek. Syarat algoritma ini adalah bobot sisinya yang harus non-negatif,
Properti Algoritma Djikstra
- Matriks Ketetangga M [mij] mij = bobot sisi (i,j) ;
pada graf tak berarah mij = mji
mii = 0 jikatidak ada sisi dari simpul i ke simpul j - 2.Larik S = [si] yang dalam hal ini,
si = 1, jika simpul i termasuk ke dalam lintasan terpendek
si = 0, jika simpul i tidak termasuk ke dalam lintasan terpendek - Larik / tabel D = [di] yang dalam hal ini, di = panjang lintasan dari simpul awal s ke simpul I.
Pseducode
function Dijkstra(Graph, source): for each vertex v in Graph: // Initializations dist[v] := infinity ; // Unknown distance function from // source to v previous[v] := undefined ; // Previous node in optimal path end for // from source dist[source] := 0 ; // Distance from source to source Q := the set of all nodes in Graph ; // All nodes in the graph are // unoptimized - thus are in Q while Q is not empty: // The main loop u := vertex in Q with smallest distance in dist[] ; // Start node in first case remove u from Q ; if dist[u] = infinity: break ; // all remaining vertices are end if // inaccessible from source for each neighbor v of u: // where v has not yet been // removed from Q. alt := dist[u] + dist_between(u, v) ; if alt < dist[v]: // Relax (u,v,a) dist[v] := alt ; previous[v] := u ; decrease-key v in Q; // Reorder v in the Queue end if end for end while return dist;
Implementasi Algoritma Dijkstra Dengan Java
sumber :
http://id.wikipedia.org/wiki/Algoritma_Dijkstra
http://sraportofolio.blogspot.com/2013/03/algoritma-dijsktra.html
http://affanw.blogspot.com/2013/05/algoritma-dijkstra.html
Label: Algoritma
0 Komentar:
Posting Komentar
Berlangganan Posting Komentar [Atom]
<< Beranda