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