Perbandingan Algoritma Ford-Fulkerson, Edmonds-Karp dan Push-Relabel dalam Menentukan Aliran Maksimum

Masalah aliran maksimum adalah permasalahan optimasi dengan tujuan mengetahui nilai aliran di dalam sebuah jaringan aliran (network flow). Jaringan aliran merupakan sebuah graf yang memiliki aliran (flow) pada setiap sisinya yang memenuhi syarat 0≤f(u,v)≤c(u,v). Masalah aliran maksimum dapat diselesaikan menggunakan beberapa algoritma diantaranya algortima Ford-Fulkerson, Edmonds-Karp dan Push-Relabel. Dalam skripsi ini ketiga metode tersebut akan dibandingkan dalam tiga aspek yang berbeda yaitu kompleksitas waktu, kesederhanaan, dan jumlah iterasi yang diperlukan untuk menentukan aliran maksimum baik secara manual maupun dengan menggunakan program python. Dengan adanya program python tersebut, masalah aliran maksimum dalam sebuah jaringan dapat ditentukan dengan cepat. Hasil dari program python telah dibandingkan dengan hasil yang diperoleh secara manual yang menunjukkan bahwa program python tidak salah. Ketiga algortima memberikan hasil yang sama dalam mencari aliran maksimum akan tetapi Ford-Fulkerson lebih sederhana dalam pencarian lintasan dibandingkan dengan Edmonds-Karp meskipun jumlah iterasi yang dibutuhkan Edmonds-Karp lebih sedikit. Berbeda dengan algortima Ford-Fulkerson dan Edmonds-Karp, pada algoritma Push-Relabel tidak menggunakan lintasan yang mana aliran tidak langsung dikirimkan dari titik sumber ke titik tujuan tetapi di alirkan ke titik yang bertetangga sehingga algoritma ini lebih mudah di terapkan untuk network yang besar walaupun membutuhkan lebih banyak iterasi.