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
