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 sama sekali 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.

Algoritme Dijkstra, (dinamai menurut penemunya, seorang ilmuwan komputer, Edsger Dijkstra), adalah sebuah algoritme 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, ${\displaystyle [0,\infty )}$. Input algoritme ini adalah sebuah graf berarah yang berbobot (weighted directed graph) ${\displaystyle G}$ dan sebuah titik asal ${\displaystyle s}$ dalam himpunan garis ${\displaystyle V}$.

Misalnya, bila titik dari sebuah graf melambangkan kota-kota dan bobot garis melambangkan jarak antara kota-kota tersebut, algoritme 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 ${\displaystyle s}$ dan ${\displaystyle t}$ dalam ${\displaystyle V}$, algoritme ini menghitung jarak terpendek dari ${\displaystyle s}$ ke ${\displaystyle t}$.

 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[]

• 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.

• Breadth-first search
• Open shortest path first

• Teori Jalan Terpendek Dijkstra oleh Jeremy Siek, dari Universitas Indiana
• Animation of Dijkstra's algorithm
• The Boost Graph Library (BGL)
• JavaScript Dijkstra's Algorithm Diarsipkan 2006-07-02 di Wayback Machine.
• Interactive Implementation of Dijkstra's Algorithm
• Shortest Path Problem: Dijkstra's Algorithm Diarsipkan 2007-09-27 di Wayback Machine.
• Dijkstra's Algorithm Applet