Algoritma Dijkstra merupakan sebuah algoritma yang dipakai untuk memecahkan permasalahan jarak terpendek (shortest path problem) dalam sebuah graf berarah (directed graph) dengan bobot-bobot sisi (edge weights) yang bernilai tak-negatif.
Apa yang dimaksud dengan Algoritma Dijkstra ?
Algoritma Dijkstra ditemukan oleh Edsger W. Dijkstra merupakan salah satu varian bentuk algoritma populer dalam pemecahan persoalan yang terkait dengan masalah optimasi dan bersifat sederhana. Algoritma ini menyelesaikan masalah untuk mencari lintasan terpendek ( sebuah lintasan yang mempunyai panjang minimum) dari vertex a ke vertex z dalam graf berbobot, bobot tersebut adalah bilangan positif jadi tidak dapat dilalui oleh vertex negatif.
Dalam mencari solusi, Algoritma Dijkstra menggunakan prinsip greedy, yaitu mencari solusi optimum pada setiap langkah yang dilalui dengan tujuan untuk mendapatkan solusi optimum pada langkah selanjutnya yang akan mengarah pada solusi terbaik.
Algoritma ini mencari panjang lintasan terpendek dari vertex a ke z dalam sebuah graf berbobot.
Langkah-langkah dalam menentukan lintasan terpendek pada Algoritma Dijkstra adalah sebagai berikut :
Pada awalnya pilih vertex dengan bobot yang terendah dari vertex yang belum dipilih, diinisialisasikan dengan ‘0’ dan yang sudah terpilih diinisialisasikan dengan ‘1’.
Bentuk tabel yang terdiri dari vertex , status, bobot. Lengkapi kolom bobot yang diperoleh dari jarak vertex sumber ke semua vertex yang langsung terhubung dengan vertex sumber tersebut.
Jika vertex sumber ditemukan maka tetapkan sebagai vertex terpilih.
Tetapkan vertex terpilih dengan label permanen dan perbaharui vertex yang langsung terhubung.
Tentukan vertex sementara yang terhubung pada vertex yang sudah terpilih sebelumnya dan merupakan bobot terkecil dilihat dari tabel dan tentukan sebagai vertex terpilih berikutnya.
Apakah vertex yang terpilih merupakan vertex tujuan? Jika ya, maka kumpulan vertex
terpilih merupakan rangkaian yang menunjukkan lintasan terpendek.
Begitu seterusnya hingga semua vertex terpilih.
Pseudocode Algoritma Dijkstra
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;