Maximum flow'ni topiş jarayonida, ba'zida yeçimga erişiş uçun allaqaçon berilgan flow'ni kamaytiriş hisobiga boşqa (parallel) edge'da flow'ni oşiriladi. Inson közi bilan körib, qaysi flow'ni kamaytiriş, qaysi flow'ni oşirişni özi aniqlab olişi mumkin, lekin kodda nima qilişni qanday ifodalaymiz?

Nima haqida aytayotganim haqida batafsil tuşuntiraman. Demak, oldingi mavzudagi kabi, bizdagi boşlanğiç graph:

Ötgan mavzuda biz flow hisoblaşni s -> 0 -> 3 -> t dan boşlagandik. Bu safar s -> 0 -> 4 -> t ga birinçi bölib flow qiymatini beramiz:

Max flow = 10

s -> 0 edge töldi (flow = capacity).

Keyingi qadam s -> 0 -> 2 -> 5 -> t, path uçun max flow 10 ga teng.

Max flow = 20

t ga inflow uçun böş edge faqat 3 -> t qoldi. Lekin 3 vertax'ni öz içiga olgan s -> 0 -> 3 -> t path'da s -> 0 tölgan, path uçun 10 flow 0 -> 4 edge orqali ketyapti. Biz 0 -> 4 edge'dan 9 flow'ni orqaga qaytarib, uni 0 -> 3 edge'dan yuborsak bölarmikin:

Max flow = 20

Flow'ni ikkiga bölganimizning yaxşi tarafi - 4 -> t edge'da 9 flow uçun joy oçildi, avval 10/10 edi, hozir 1/10. Biz böşagan edge'dan unumli foydalanişga urinamiz:

s -> 1 -> 4 -> t path'ga 5 flow beramiz:

Max flow = 25

s -> 2 -> 5 -> 1 -> 4 -> t path'ga 3 flow beramiz:

Max flow = 28

Maximum flow 28 ga teng çiqdi.

---

Biz flow'ni orqaga qaytarib boşqa edge'ga bölişni özimiz fikrlab amalga oşirdik. Kodga esa işlaşi uçun flow'ni böliş, orqaga qaytariş kabi fikrlaşni "çaynab" solib qöyişimiz kerak. Buning uçun bizga özgarişlarni qayd etib borişga yana bir graph - residual graph zarur böladi.

Umumiy holda, Ford-Fulkerson algoritmi ikki konseptga asoslanadi.

1. Residual graph (yoki residual network)
2. Augmenting path

Residual graph

Residual graph (yoki residual network) - original graph'dagi kabi vertex'larga ega va vertex'lari bitta yoki ikkita edge bilan boğlangan graph. U graph'da qöşimça ehtimoliy flow'larni (addditional flow) aniqlab beradi.

Har bir edge uçun qöşimça flow'larni quyidagiça hisoblaymiz:

Additional flow = edge capacity — edge flow

Residual graph'ni hosil qiliş uçun original graph'ni olib, har bir edge'ning capacity'siga edge uçun additional flow qiymatini beramiz. Agar original graph'dagi edge'da flow qiymati 0 dan katta bölsa, residual graph'da mos holda ikki vertex uçun reverse edge qöşib çiqamiz.

• Original (böş) graph
• Residual graph

s -> 0 -> 4 -> t path'ga flow bersak:

• 
• 

Reverse edge'ni yana backward edge ham deyiladi.

Augmenting path

Augmenting path - residual graph'da s dan t gaça boradigan ehtimoliy path. Masalan yuqoridagi misolda augmenting path - s -> 2 -> 5 -> t bölişi mumkin, sababi uşbu path original graph'da hali böş.

Maximum flow topilgan graph'da augmenting path bölmaydi.

Algoritmning işlaş tartibi

1. Barça edge'larga 0 qiymat bilan boşlaydi
2. s dan t gaça edge'larga flow berib augmenting path borligini tekşiradi.
3. Agar bor bölsa flow'ni qaytaradi

Kod