MEMBANDINGKAN KEMANGKUSAN ALGORITMA DINIC DAN ALGORITMA PELABELAN FORD-FULKERSON UNTUK MASALAH ARUS MAKSIMUM

Abstract

Teori graf merupakan salah satu cabang matematika yang paling banyak aplikasinya dalam kehidupan sehari-hari. Salah satu bentuk dari graf adalah jaringan (network), yaitu graf berarah berbobot sederhana yang memiliki simpul sumber (source), simpul tujuan (sink), dan tiap sisinya mempunyai kapasitas tertentu. Algoritma Dinic dan algoritma Pelabelan Ford-Fulkerson merupakan algoritma yang digunakan dalam pemecahan masalah arus maksimum.         Algoritma Dinic memanfaatkan jaringan sisa. Pada jaringan sisa ini diidentifikasi f-augmenting path terpendek melalui layered network, kemudian dikonstruksi suatu blocking flow yang dapat digunakan untuk menentukan arus maksimum. Algoritma pelabelan Ford-Fulkerson berisi 2 fase. Fase pertama melakukan pelabelan untuk memeriksa apakah terdapat f-augmenting path. Jika terdapat f-augmenting path, maka menentukan dan menambahkan f-augmenting path pada arus f. Algoritma Dinic dan algoritma pelabelan Ford-Fulkerson memberikan solusi arus maksimum yang sama yaitu sebanyak 7. Algoritma pelabelan Ford-Fulkerson lebih mangkus dibandingkan dengan algoritma Dinic karena algoritma pelabelan Ford-Fulkerson membutuhkan waktu dan ruang memori yang lebih sedikit dalam mencari solusi dari masalah arus maksimum.

Kata kunci: algoritma pelabelan ford-fulkerson, algoritma dinic, masalah arus maksimum, jaringan