Skip to content
Kembali ke hasil pencarian

Algoritma Ford-Fulkerson

Diperkenalkan oleh
Lester R. Ford and Delbert R. Fulkerson
Tahun
1956
Jenis
algorithm
Keluarga
Graph Algorithms

Teks ini adalah terjemahan mesin dan belum ditinjau. Baca versi asli dalam bahasa Inggris

Ukuran huruf

Apa fungsinya?

Algoritma Ford-Fulkerson, yang dikembangkan oleh Lester R. Ford dan Delbert R. Fulkerson pada tahun 1956, adalah metode fundamental untuk menghitung aliran maksimum dalam jaringan aliran.

Algoritma ini menemukan jumlah aliran maksimum yang dapat dikirim dari sumber ke tujuan melalui graf berarah dengan batasan kapasitas pada sisi-sisinya.

Intuisi di balik metode

Algoritma bekerja dengan berulang kali menemukan jalur penambah (augmenting paths) dari sumber ke tujuan melalui jaringan residual, di mana setiap sisi memiliki kapasitas yang tersisa. Setiap jalur berkontribusi aliran tambahan yang setara dengan kapasitas gentingnya (sisi dengan kapasitas residual minimum pada jalur tersebut). Proses ini berlanjut hingga tidak ada lagi jalur penambah yang ada, pada titik tersebut aliran maksimum tercapai. Wawasan kunci adalah teorema aliran maksimum-pemotongan minimum (max-flow min-cut theorem): aliran maksimum sama dengan kapasitas pemotongan minimum dalam jaringan.

Sejarah

Ford dan Fulkerson memperkenalkan masalah aliran maksimum dan algoritma seminal mereka pada tahun 1956. Karya tersebut revolusioner, menetapkan metode algoritmik dan teorema aliran maksimum-pemotongan minimum yang terkenal. Edmonds dan Karp (1972) meningkatkan kompleksitas kasus terburuk dengan menggunakan pencarian lebar pertama untuk pemilihan jalur. Kemajuan selanjutnya oleh Dinic, Karzanov, dan lainnya menghasilkan algoritma yang lebih cepat, tetapi metode Ford-Fulkerson tetap menjadi algoritma klasik dan bernilai pedagogis dalam ilmu komputer.

Kapan digunakan

Terapkan algoritma Ford-Fulkerson untuk menemukan aliran maksimum dalam jaringan aliran berarah atau tak berarah dengan kapasitas bilangan bulat positif. Algoritma ini bekerja dengan baik untuk jaringan berukuran kecil hingga menengah dan memberikan pemahaman intuitif tentang konsep aliran jaringan. Untuk jaringan yang sangat besar atau ketika aliran integral diperlukan, pertimbangkan algoritma Edmonds-Karp (menggunakan BFS) atau algoritma Dinic untuk kinerja kasus terburuk yang lebih baik. Gunakan algoritma ini ketika pemahaman perilaku algoritma sama pentingnya dengan kecepatan.

Batasan dan pertimbangan

  • Kompleksitas waktu bergantung pada nilai kapasitas (umumnya tidak polinomial; bisa eksponensial dengan kapasitas irasional)
  • Mungkin tidak berhenti jika kapasitas bersifat irasional (memerlukan implementasi yang cermat dengan aritmatika rasional)
  • Kurang efisien dibandingkan algoritma khusus seperti Edmonds-Karp atau Dinic pada jaringan besar
  • Sensitif terhadap urutan pemilihan jalur penambah

Syarat dari sumber tidak menggantikan tinjauan ilmiah independen atau validasi oleh mesin analisis.

Kelebihan

  • Pendekatan sederhana dan intuitif berdasarkan jalur penambah
  • Solusi optimal terjamin ketika kapasitas bersifat rasional atau integral
  • Efisien untuk jaringan dengan kapasitas bilangan bulat kecil
  • Membentuk dasar teoretis untuk memahami dualitas aliran maksimum-pemotongan minimum
  • Bekerja dengan graf berarah dan tak berarah

Penerapan

  • Perutean jaringan: memaksimalkan throughput data dari sumber ke tujuan dalam jaringan komunikasi
  • Jaringan transportasi: menentukan kapasitas kargo maksimum antara kota dengan mempertimbangkan batasan jalan dan rel
  • Pencocokan bipartit: menemukan pencocokan maksimum dalam graf bipartit dengan membangun jaringan aliran
  • Segmentasi gambar: menggunakan algoritma aliran maksimum untuk mempartisi gambar menjadi latar depan dan latar belakang
  • Penjadwalan maskapai penerbangan: mengoptimalkan perutean pesawat untuk memaksimalkan aliran penumpang melalui jaringan hub-and-spoke
  • Analisis protein: menghitung aliran maksimum dalam jaringan biologis untuk memahami jalur interaksi

Cara kerjanya

Cara kerjanya

1

Inisialisasi graf residual dengan kapasitas yang sama dengan kapasitas sisi asli dan aliran nol pada semua sisi.

2

Temukan jalur penambah dari sumber ke tujuan dalam graf residual menggunakan pencarian kedalaman pertama (depth-first search) atau pencarian lebar pertama (breadth-first search), hitung kapasitas minimum di sepanjang jalur, dan tambahkan aliran ini ke semua sisi pada jalur sambil mengurangi kapasitas residualnya.

3

Ulangi penambahan hingga tidak ada jalur penambah yang ada dalam graf residual; total aliran yang terakumulasi adalah aliran maksimum.

Kesalahan umum

  • Memilih jalur penambah yang buruk yang menghasilkan konvergensi lambat atau hasil yang salah
  • Gagal memperbarui kapasitas residual dengan benar atau menambahkan sisi balik untuk membatalkan aliran
  • Menggunakan pembagian bilangan bulat atau aritmatika titik mengambang ketika aritmatika eksak diperlukan untuk kebenaran

Pertanyaan yang sering diajukan

Apa itu teorema aliran maksimum-pemotongan minimum?

Teorema tersebut menyatakan bahwa aliran maksimum dari sumber ke tujuan sama dengan kapasitas minimum dari setiap pemotongan yang memisahkan sumber dari tujuan. Ini memberikan wawasan teoretis dan metode verifikasi untuk algoritma aliran.

Mengapa algoritma terkadang konvergen lambat?

Dengan pemilihan jalur yang tidak menguntungkan, algoritma mungkin hanya menambah satu unit aliran per iterasi, bahkan ketika penambahan yang lebih besar dimungkinkan. Menggunakan pencarian lebar pertama (Edmonds-Karp) memastikan konvergensi waktu polinomial.

Bagaimana algoritma menangani sisi tak berarah?

Ganti setiap sisi tak berarah dengan dua sisi berarah yang berlawanan arah, keduanya dengan kapasitas yang sama. Algoritma kemudian menemukan aliran pada jaringan berarah.

Apa perbedaan antara aliran pada sisi dan kapasitas residual?

Aliran pada sisi mewakili jumlah material yang dikirim melaluinya, sedangkan kapasitas residual adalah kapasitas yang tersisa. Kapasitas residual berkurang seiring bertambahnya aliran, dan sisi balik melacak kemampuan untuk membatalkan aliran.

Metode terkait

Sumber

  1. Ford, L. R., & Fulkerson, D. R. (1956). Maximal flow through a network. Canadian Journal of Mathematics, 8(3), 399-404.

    Buka referensi DOI
    Disalin.
  2. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.

    ISBN: 978-0-262-03384-8
    Disalin.