My first Magazine pemrograman-kompetitif-dasar | Page 135

11.1 Shortest Path
Untuk kasus terburuk, seluruh node dapat dicapai dari s sehingga terdapat V iterasi. Pada
setiap iterasi, dilakukan pencarian node untuk di-relax dan proses relax . Algoritma 62 menun-
jukkan pencarian node untuk di-relax yang diimplementasikan dengan linear search , sehingga
kompleksitas sekali pencariannya adalah O(V ). Untuk proses relax sendiri, total kompleksitas-
nya ketika seluruh node di-relax adalah O(E). Kompleksitas total untuk implementasi ini adalah
O(V 2 + E). Kompleksitas ini juga dapat dituliskan sebagai O(V 2 ) saja, sebab banyaknya edge
dibatasi oleh V 2 .
Optimisasi dengan heap
Pencarian node untuk di-relax sebenarnya merupakan pencarian nilai terkecil dari suatu
kumpulan. Kita dapat menggunakan struktur data heap untuk membuat pencarian ini lebih efisien,
yaitu O(logV ) per pencarian.
Heap yang kita perlukan adalah min -heap , yang menyimpan daftar node yang terurut
berdasarkan jarak tempuh sejauh ini. Untuk mempermudah implementasi, kita dapat membuat
heap yang dapat menyimpan elemen berupa pasangan data h jarak, nodei. Setiap kali jarak
tempuh suatu node diperbaharui, masukkan datanya ke dalam heap . Hal ini memungkinkan heap
menyimpan beberapa node yang sama dengan jarak yang berbeda. Tidak menjadi masalah, sebab
ketika hasil pop heap adalah node yang sudah dikunjungi, kita cukup mengabaikannya. Algoritma
64 menunjukkan implementasi yang dioptimisasi dengan heap .
Algoritma 64 Implementasi algoritma Dijkstra dengan optimisasi heap .
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: INITIALIZE H EAP ()
9: PUSH (h0, si)
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
. Buat sebuah min-heap
. Masukkan node s dengan jarak tempuh 0 ke dalam heap
dist[s] ← 0
while not IS E MPTY H EAP () do
hcurDist, ui ← POP ()
. Dapatkan node yang jarak tempuhnya terkecil
if not visited[u] then
. Hanya proses apabila u belum dikunjungi
visited[u] ← true
for v ∈ ad j(u) do
. Lakukan relax untuk semua tetangga u
if dist[v] > dist[u] + w[u][v] then
dist[v] = dist[u] + w[u][v]
pred[v] = u
PUSH (hdist[v], vi) . Masukkan jarak dan node yang diperbaharui ke heap
end if
end for
end if
end while
return dist
end function
125