My first Magazine pemrograman-kompetitif-dasar | Page 137

11.1 Shortest Path
5:
6:
7:
8:
9:
10:
11:
12:
13:
for i ← 1, V − 1 do
for hu, vi ∈ edgeList do
if dist[v] > dist[u] + w[u][v] then
dist[v] = dist[u] + w[u][v]
end if
end for
end for
return dist
end function
Algoritma 66 Pendeteksian negative cycle dengan memanfaatkan hasil pencarian shortest path
menggunakan Bellman—Ford.
function HAS N EGATIVE C YCLE (s)
2:
dist ← B ELLMAN -F ORD (s)
1:
3:
4:
5:
6:
7:
8:
9:
for hu, vi ∈ edgeList do
if dist[v] > dist[u] + w[u][v] then
return true
end if
end for
return f alse
end function
Terdapat V − 1 tahapan relaksasi edge , yang mana setiap relaksasi bekerja dalam O(E).
Secara jelas, kita dapat memperhatikan bahwa kompleksitas algoritma Bellman—Ford adalah
O(V E). Meskipun lebih lambat daripada Dijkstra, algoritma ini bersifat lebih umum.
11.1.3
Floyd—Warshall
Konsep
Kadang-kadang, kita membutuhkan informasi shortest path dari setiap node ke setiap node
lainnya pada suatu graf. Selain dengan menjalankan Dijkstra atau Bellman—Ford satu per satu
untuk setiap node , kita juga dapat menggunakan algoritma Floyd—Warshall.
Konsep dari algoritma ini adalah dynamic programming . Definisikan sebuah fungsi f (i, j, k)
yang menyatakan jarak terpendek untuk berpindah dari node i ke node j, dengan hanya menggu-
nakan node -node perantara {1, 2, 3, ..., k}. Nilai dari f (i, j, k) merupakan salah satu yang terkecil
dari:
• Jarak terpendek dari i ke j, apabila tidak menggunakan k sebagai perantaranya. Nilai ini
sama dengan f (i, j, k − 1).
• Jarak terpendek dari i ke j, apabila k digunakan sebagai perantaranya. Jaraknya adalah jarak
i ke k, ditambah k ke j, dengan masing-masing hanya boleh menggunakan {1, 2, 3, ..., k − 1}
sebagai perantaranya. Nilai ini sama dengan f (i, k, k − 1) + f (k, j, k − 1).
Kasus ketika perpindahan i ke j tidak boleh menggunakan perantara menjadi base case .
Kasus ini terjadi ketika k = 0, yang artinya node perantara yang boleh digunakan berupa himpunan
kosong. Pada kasus ini, f (i, j, 0) = w[i][ j].
127