My first Magazine pemrograman-kompetitif-dasar | Page 134

11 Algoritma Graf
Algoritma 62 Implementasi algoritma Dijkstra.
1:
2:
3:
4:
5:
6:
7:
function D IJKSTRA (s)
dist ← new integer[V + 1]
visited ← new boolean[V + 1]
pred ← new integer[V + 1]
FILL A RRAY (dist, ∞)
FILL A RRAY (visited, f alse)
FILL A RRAY (pred, −1)
8:
dist[s] ← 0
while true do
. Perulangan ini akan diakhiri dengan break
u ← −1
minDist ← ∞
for i ← 1, V do
. Cari node yang belum dikunjungi dan memiliki dist terkecil
if (not visited[i]) ∧ (dist[i] < minDist) then
u ← i
minDist ← dist[i]
end if
end for
if (u = −1) ∨ IS I NFINITE (dist[u]) then
break
. Akhiri perulangan while
end if
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
visited[u] ← true
for v ∈ ad j(u) do
if dist[v] > dist[u] + w[u][v] then
dist[v] = dist[u] + w[u][v]
pred[v] = u
end if
end for
end while
22:
23:
24:
25:
26:
27:
28:
return dist
30: end function
29:
. Lakukan relax untuk semua tetangga u
. Kembalikan tabel shortest path yang bermula dari s
Untuk mencetak edge -edge yang perlu dilalui untuk mencapai suatu node x dari node
permulaan (yaitu s), cukup lakukan penelusuran dari x ke belakang menggunakan informasi pred[x]
sampai mencapai s. Algoritma pencariannya ditunjukkan pada Algoritma 63. Waspadai bahwa
belum tentu semua node x dapat dikunjungi dari s. Ketika hal ini terjadi, pred[x] masih tetap
bernilai −1.
Algoritma 63 Mencetak edge -edge yang dilalui untuk mencapai node x.
1:
2:
3:
4:
5:
6:
7:
8:
procedure PRINT P ATH (x)
if (pred[x] = −1) ∧ (x 6 = s) then
print "Tidak ada jalan"
else if pred[x] 6 = −1 then
PRINT P ATH (pred[x])
print pred[x], x
end if
end procedure
124