Algoritma Dijkstra
Artikel ini perlu diterjemahkan ke bahasa Indonesia. Artikel ini ditulis atau diterjemahkan secara buruk dari Wikipedia bahasa selain Indonesia. Jika halaman ini ditujukan untuk komunitas berbahasa tersebut, halaman itu harus dikontribusikan ke Wikipedia bahasa tersebut. 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 greedy algorithm yang memecahkan shortest path problem untuk sebuah directed graph dengan edge weights yang tidak negatif.
Misalnya, bila vertices dari sebuah graph melambangkan kota-kota dan edge weights melambangkan jarak antara kota-kota tersebut, algoritma Dijkstra dapat digunakan untuk menemukan jarak terpendek antara dua kota.
Input algoritma ini adalah sebuah weighted directed graph G dan sebuah source vertex s dalam G. V adalah himpunan semua vertices dalam graph G. Setiap edge dari graph ini adalah pasangan vertices (u,v) yang melambangkan hubungan dari vertex u ke vertex v. Himpunan semua edge disebut E. Weights dari edges dihitung dengan fungsi w: E → [0, ∞); jadi w(u,v) adalah jarak non-negatif dari vertex u ke vertex v. Cost dari sebuah edge dapat dianggap sebagai jarak antara dua vertex, yaitu jumlah jarak semua edge dalam path 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.