Algoritma Dijkstra

(Dialihkan dari Algoritme Dijkstra)

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, . Input algoritme ini adalah sebuah graf berarah yang berbobot (weighted directed graph) dan sebuah titik asal dalam himpunan garis .

Algoritme Dijkstra

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 dan dalam , algoritme ini menghitung jarak terpendek dari ke .

Kode semu

sunting
 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

sunting

Lihat pula

sunting

Pranala luar

sunting