Banyak masalah dalam ilmu komputer dapat direpresentasikan oleh grafik yang terdiri dari node dan keterkaitan di antara keduanya. Contohnya adalah masalah aliran jaringan, yang mengangkut barang atau material di seluruh jaringan, seperti sistem kereta api.
Anda dapat merepresentasikan alur jaringan dengan grafik yang node-nya adalah kota dan busurnya berbentuk garis rel di antara keduanya. (Disebut flow karena propertinya mirip dengan air yang mengalir melalui jaringan pipa.)
Batasan utama dalam alur jaringan adalah bahwa setiap busur memiliki kapasitas — jumlah maksimum yang dapat diangkut melintasi busur dalam jangka waktu tetap.
Masalah flow maksimum adalah menentukan jumlah total maksimum yang dapat diangkut di semua busur dalam jaringan, yang tunduk pada batasan kapasitas.
Orang pertama yang mempelajari masalah ini adalah ahli matematika Rusia, A.N. Tolstoi, pada tahun 1930-an. Peta di bawah ini menunjukkan jaringan kereta api sebenarnya yang ingin ditemukan alur maksimumnya.
OR-Tools menyediakan beberapa pemecah masalah untuk masalah aliran jaringan dalam library grafik-nya.
Bagian berikut menampilkan contoh masalah alur jaringan dan menunjukkan cara menyelesaikannya: