Algoritma Dijkstra
Artikel ini perlu diterjemahkan dari bahasa Inggris ke bahasa Indonesia. Artikel ini ditulis atau diterjemahkan secara buruk dari Wikipedia bahasa Inggris. Jika halaman ini ditujukan untuk komunitas bahasa Inggris, halaman itu harus dikontribusikan ke Wikipedia bahasa Inggris. Lihat daftar bahasa Wikipedia. Artikel yang tidak diterjemahkan dapat dihapus secara cepat sesuai kriteria A2. Jika Anda ingin memeriksa artikel ini, Anda boleh menggunakan mesin penerjemah. Namun ingat, mohon tidak menyalin hasil terjemahan tersebut ke artikel, karena umumnya merupakan terjemahan berkualitas rendah. |
Algoritma Dijkstra, dinamai menurut penemunya, Edsger Dijkstra, adalah sebuah algoritma rakus (greedy algorithm) dalam memecahkan permasalahan jarak terpendek (shortest path problem) untuk sebuah graf terarah (directed graph) dengan bobot-bobot tepi (edge weights) yang bernilai tak-negatif.
Misalnya, bila vertices dari sebuah graf melambangkan kota-kota dan bobot tepi (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 terarah yang berbobot (weighted directed graph) G dan sebuah sumber vertex s dalam G dan V adalah himpunan semua vertices dalam graph G.
Setiap tepi (edge) dari graf ini adalah pasangan vertices (u,v) yang melambangkan hubungan dari vertex u ke vertex v. Himpunan semua edge disebut E.
Bobot (weights) dari semua tepi dihitung dengan fungsi
w: E → [0, ∞)
jadi w(u,v) adalah jarak tak-negatif dari vertex u ke vertex v.
Ongkos (cost) dari sebuah tepi dapat dianggap sebagai jarak antara dua vertex, yaitu jumlah jarak semua tepi dalam jalur tersebut. Untuk sepasang vertex s dan t dalam V, algoritma ini menghitung jarak terpendek dari s ke t.
Pseudocode
1 function Dijkstra(G, w, s)
2 for each vertex v in V[G] // Initializations
3 d[v] := infinity
4 previous[v] := undefined
5 d[s] := 0 // Distance from s to s
6 S := empty set
7 Q := V[G] // Set of all vertices
8 while Q is not an empty set // The algorithm itself
9 u := Extract_Min(Q)
10 S := S union {u}
11 for each edge (u,v) outgoing from u
12 if d[u] + w(u,v) < d[v] // Relax (u,v)
13 d[v] := d[u] + w(u,v)
14 previous[v] := u
Rujukan
- E. W. Dijkstra: A note on two problems in connexion with graphs. In: Numerische Mathematik. 1 (1959), S. 269–271
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 24.3: Dijkstra's algorithm, pp.595–601.