Algoritma Dijkstra

Algoritma Dijkstra, (dinamai menurut penemunya, seorang ilmuwan komputer, Edsger Dijkstra), adalah sebuah algoritma rakus (greedy algorithm) yang dipakai dalam memecahkan permasalahan jarak terpendek (shortest path problem) untuk sebuah graf berarah (directed graph) dengan bobot-bobot garis (edge weights) yang bernilai nonnegatif, . Input algoritma ini adalah sebuah graf berarah yang berbobot (weighted directed graph)  dan sebuah titik asal  dalam himpunan garis .

Misalnya, bila titik dari sebuah graf melambangkan kota-kota dan bobot garis melambangkan jarak antara kota-kota tersebut, algoritma Dijkstra dapat digunakan untuk menemukan jarak terpendek antara dua kota.

Biaya (cost) dari sebuah garis dapat dianggap sebagai jarak antara dua simpul, yaitu jumlah jarak semua garis dalam jalur tersebut. Untuk sepasang titik  dan  dalam , algoritma ini menghitung jarak terpendek dari  ke .

 Kode semu 
  1  fungsi Dijkstra(Graf, asal):
  2      Q adalah himpunan titik
  3
  4      untuk setiap titik v dalam Graf:
  5          jarak[v] ← tak hingga
  6          sebelum[v] ← kosong
  7          tambahkan v ke dalam Q
  8      jarak[asal] ← 0;
  9
 10      selama Q tidak kosong:
 11          u ← titik dalam Q dengan nilai jarak[u] terkecil
 12          hapus u dari Q
 13
 14          untuk setiap tetangga v dari u: // hanya v yang masih dalam Q
 15              alt ← jarak[u] + jarak_antara(u, v)
 16              jika alt < jarak[v]:
 17                  jarak[v] ← alt
 18                  sebelum[v] ← u
 19
 20  kembalikan jarak[], sebelum[]

 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.

 Lihat pula 
 Breadth-first search
 Open shortest path first

 Pranala luar 
 Teori Jalan Terpendek Dijkstra oleh Jeremy Siek, dari Universitas Indiana
 Animation of Dijkstra's algorithm
 The Boost Graph Library (BGL)
 JavaScript Dijkstra's Algorithm 
 Interactive Implementation of Dijkstra's Algorithm
 Shortest Path Problem: Dijkstra's Algorithm 
 Dijkstra's Algorithm Applet

Dijkstra