“Floyd algoritmi” mavzusidagi

2.1.Maksimal oqimni topish algoritmi.
Ushbu algoritm g„oyasi manbaadan to quyilish joyigacha bo„lgan musbat oqimli o„tish yo„lini topishdir. Сij , C ji (boshlang„ich) o„tkazish qobiliyatli (i,j) qirrani qaraylik. Algoritm bajarilish jarayonida ushbu o„tkazish qobiliyatlarining bir qismi mazkur qirradan o„tuvchi oqim tomonidan “ushlab qolinadi” va natijada har bir qirra qoldiq o„tkazish qobiliyatiga ega bo„ladi. c_ij , c _ji - yozuvni qoldiq o„tkazish qobiliyatini tasvirlash uchun ishlatamiz.

Ta’rif. Barcha qirralari qoldiq o„tkazish qobiliyatiga ega bo„lgan tarmoq qoldiq tarmoq deyiladi.

1. 
   tugundan oqim oluvchi ixtiyoriy j tugun uchun а _j ,i nishonni aniqlaymiz. Bu yerda a _j j tugundan i tugunga oquvchi oqim miqdori.
   

Algoritmning ishlash sxemasi quyidagicha:
1-qadam. Barcha (i,j) qirralar uchun dastlabki o„tkazish qobiliyatiga teng

qoldiq o„tkazish qobiliyatini joylashtiramiz, ya‟ni сij , с ji				ij ,		ji	. a1deb olib
			C		C
1-tugunni , 1 nishon bilan belgilaymiz. i=1 deb qabul qilamiz va 2-qadamga
o„tamiz.