PENERAPAN ALGORITMA EDMONDS-KARP DALAM PENCARIAN ALIRAN MAKSIMUM PADA PENDISTRIBUSIAN AIR - Margaretha, Silvya; Kiftiah, Mariatul; Helmi, Helmi (FMIPA Universitas Tanjungpura, 2024)
Graf merupakan representasi matematis dari sebuah jaringan dan menggambarkan hubungan antar sejumlah simpul yang terhubung dengan busur. Permasalahan yang dibahas pada penelitian ini mengenai kasus pendistribusian air suatu motel yang direpresentasikan dengan graf berarah, dengan setiap busurnya mempunyai bobot. Tujuan dari penelitian ini yaitu memaksimalkan debit air yang mengalir melewati sistem jaringan distribusi air pada motel dari simpul sumber ke simpul tujuan. Permasalahan tersebut diselesaikan dengan menggunakan algoritma Edmonds-Karp. Algoritma ini dimulai tanpa adanya aliran di semua busur. Kemudian, dicari jalur penambah yaitu jalur berarah yang menghubungkan simpul awal dan simpul tujuan, dengan menggunakan algoritma Breadth-first search (BFS). Algoritma BFS menelusuri setiap simpul secara berurutan, mulai dari simpul awal dikunjungi hingga simpul-simpul yang bertetangga dengannya dikunjungi, sesuai urutan antrian. Selanjutnya, mencari kapasitas sisa minimum busur dari jalur penambah. kapasitas sisa minimum digunakan untuk mengoptimalkan aliran pada jalur penambah. Proses ini dilakukan hingga tidak ditemukan lagi jalur penambah dan diperoleh aliran maksimumnya. Aliran maksimum didapatkan dengan menjumlah setiap kapasitas sisa minimum jalur penambah yang diperoleh. Dari analisis menggunakan algoritma Edmonds-Karp pada jaringan distribusi air suatu motel, diperoleh aliran maksimumnya sebesar 600 liter per menit. Kata Kunci : Aliran maksimum, algoritma Edmonds-Karp, algoritma Breadth-first search (BFS).