IMPLEMENTASI ALGORITMA EDMOND-KARP PADA PENCARIAN ALIRAN MAKSIMUM - Mahesa, Nugrah; Helmi, Helmi (FMIPA Universitas Tanjungpura, 2024)
Penerapan teori graf, salah satunya dapat membantu memecahkan masalah-masalah terkait Network Flow, termasuk pencarian aliran maksimum. Aliran maksimum penting untuk menentukan batas maksimum pada aliran dalam sebuah sistem jaringan. Penelitian ini menggunakan contoh kasus pencarian aliran maksimum dalam dua konteks: jaringan listrik kota X dan pengangkutan muatan kendaraan kelapa sawit dari pabrik A ke pabrik H. Tujuan penelitian adalah memastikan bahwa jaringan listrik dan pengangkutan muatan kendaraan kelapa sawit tidak melampaui batas maksimumnya. Dalam penelitian ini, algoritma Edmond-Karp dipilih untuk memperoleh aliran maksimum. Algoritma Edmond-Karp dikenal sebagai algoritma yang efektif untuk menentukan aliran maksimum, dengan menggunakan algoritma Breadth First Search (BFS) untuk menemukan lintasan penambah yang optimal Tahap-tahap dalam pencarian aliran maksimum yaitu mengkontruksikan jaringan listrik atau muatan kendaraan ke bentuk graf, tahap kedua menginisiasi dengan menyatakan kapasitas yang mengalir pada sisi , tahap ketiga mengidentifikasi lintasan penambah dengan menggunakan Algoritma Breadth First Search, tahap keempat menentukan kapasitas residu pada lintasan penambah yang telah diperoleh, jika masih terdapat lintasan penambah yang lain maka diulangi lagi tahap ketiga. Namun jika tidak terdapat lintasan penambah, dilanjutkan tahap selanjutnya menghitung sisa kapasitas pada setiap lintasan penambah sehingga diperoleh nilai aliran maksimum pada jaringan listrik kota X diperoleh 1500 A dengan 5 lintasan penambah dan pada muatan kendaraan kelapa sawit dari pabrik A ke pabrik H sebesar 24 Ton dengan 5 lintasan penambah. Kata Kunci: Graf, Aliran Maksimum, Algoritma Edmond-Karp.