My first Magazine pemrograman-kompetitif-dasar | Page 138

11 Algoritma Graf
Dengan demikian, dapat dirumuskan DP berikut:

f (i, j, k) =
w[i][ j],
k = 0
min( f (i, j, k − 1), f (i, k, k − 1) + f (k, j, k − 1)), k > 0
Shortest path dari node s ke node t dinyatakan pada f (s,t,V ).
Implementasi
Seperti DP umumnya, kita dapat menggunakan top-down atau bottom-up . Implementasi
yang biasa digunakan adalah versi bottom-up menggunakan optimisasi flying table , karena
pendek dan mudah ditulis. Optimisasi flying table dapat dilakukan sebab perhitungan DP
f (_, _, k) hanya membutuhkan informasi f (_, _, k − 1). Representasi graf yang mudah digunakan
adalah adjacency matrix . Algoritma Algoritma 67 menunjukkan implementasinya.
Algoritma 67 Implementasi algoritma Floyd—Warshall dengan DP bottom-up .
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
function F LOYD -W ARSHALL ()
dist ← new integer[V + 1][V + 1]
FILL A RRAY (dist, ∞)
for i ← 1, V do
for j ← 1, V do
dist[i][ j] ← w[i][ j]
end for
end for
. Base case
for k ← 1, V do
. Pengisian tabel
for i ← 1, V do
for j ← 1, V do
dist[i][ j] ← min(dist[i][ j], dist[i][k] + dist[k][ j])
end for
end for
end for
. Kini dist[i][ j] berisi shortest path dari i ke j
return dist
. Kembalikan tabel DP
end function
Terlihat jelas bahwa kompleksitas waktunya adalah O(V 3 ). Meskipun lebih lambat daripada
menggunakan algoritma Dijkstra atau Bellman—Ford satu per satu, Floyd—Warshall memiliki
kelebihan dalam kemudahan implementasinya. Cukup dengan tiga lapis for ... loop, shortest
path antar setiap node ditemukan. Algoritma ini cocok digunakan apabila hanya terdapat sedikit
node , dan Anda hendak menghemat waktu pengetikan kode.
11.2
Minimum Spanning Tree
Persoalan lainnya yang cukup klasik pada permasalahan graf adalah mencari Minimum
Spanning Tree pada graf berbobot tidak berarah. Spanning Tree dari suatu graf adalah
subgraf yang mana seluruh node pada graf tersebut terhubung dan membentuk tree .
128