My first Magazine pemrograman-kompetitif-dasar | Page 136

11 Algoritma Graf
Optimisasi ini membuat kompleksitas algoritma Dijkstra berjalan dalam O((V + E) logV ).
11.1.2
Bellman—Ford
Konsep
Untuk mengatasi kekurangan algoritma Dijkstra pada graf dengan bobot negatif, kita dapat
menggunakan algoritma Bellman—Ford. Algoritma ini menerima input berupa graf dan sebu-
ah node awal, misalnya s, dan mengembalikan shortest path dari s ke seluruh node lainnya.
Algoritma ini juga memberikan kemampuan tambahan berupa pendeteksian negative cycle .
Negative cycle merupakan cycle pada graf berbobot yang jumlah bobotnya negatif. Ketika
negative cycle dapat dicapai dari suatu node awal dan dapat menuju ke suatu node akhir, maka
shortest path dari kedua node tersebut menjadi tidak terdefinisi. Sebab, perjalanan dari node
awal ke node akhir dapat berputar-putar di negative cycle sambil terus mengurangi bobot
perjalanannya. Gambar 11.9 menunjukkan contoh graf dengan negative cycle .
6
1
2
-5
4
1
2
3
3
5
2
Gambar 11.9: Contoh graf yang memiliki negative cycle , yaitu [2, 3, 4]. Shortest path dari 1 ke 5
tidak terdefinisi karena adanya negative cycle .
Ide dari algoritma Bellman—Ford adalah terus menerus melakukan proses relax , sampai
pada akhirnya tidak ada perubahan bobot perjalanan dan shortest path yang benar ditemukan.
Observasi yang dimanfaatkan algoritma ini adalah, shortest path dari suatu node ke node
lainnya dipastikan tidak melibatkan lebih dari V − 1 edge . Artinya apabila sebanyak V − 1 kali
seluruh edge di-relax , maka seluruh shortest path akan ditemukan. Dengan demikian, algoritma
ini dapat disimpulkan menjadi: sebanyak V − 1 kali, relax seluruh edge .
Untuk mendeteksi keberadaan negative cycle , kita dapat melakukan relax tambahan seba-
nyak satu kali. Jika masih terdapat bobot perjalanan yang berubah, dipastikan perubahan itu
disebabkan oleh negative cycle .
Implementasi
Representasi graf yang cocok digunakan adalah edge list atau adjacency list , untuk men-
dapatkan informasi seluruh edge secara efisien. Algoritma 65 menunjukkan implementasinya,
sementara Algoritma 66 menunjukkan fungsi tambahan untuk mendeteksi keberadaan negative
cycle .
Algoritma 65 Implementasi algoritma Bellman—Ford.
1:
2:
function B ELLMAN -F ORD (s)
dist ← new integer[V + 1]
3:
4:
126
FILL A RRAY (dist, ∞)
dist[s] ← 0