“Floyd algoritmi” mavzusidagi

2-qadam.	Si to„plami- tugundan musbat qoldiq o„tkazish
qobiliyati qirra

orqalio„tishi mumkin bo„lgan j-tugunlar to„plami sifatida aniqlanadi. (ya‟ni, с_ij 0

barcha j		Si ). Agar Si			bo„lsa 3-qadam bajariladi, aks holda 4-qadamga o„tiladi.
	3-qadam.		Si	to„plamdan сik		max ^{^cij ^}	shartni qanoatlantiruvchi k-tugun
						j Si
topiladi.		^аk^Cik		deb	olinadi va k	tugunga	ak , i nishon qo„yiladi. Agar oxirgi

nishon bilan quyilish tuguni belgilangan bo„lsa(ya‟ni, k=n), o„tish yo„li topilgan bo„ladi va 5-qadamga o„tiladi. Aks holda i=k deb olib, 2-qadamga qaytiladi.

4-qadam(ortga qaytish). Agar i=1 bo„lib, o„tishning imkoni yo„q bo„lsa, 6-qadamga o„tiladi. Agar i 1nishon qo„yilgan bevosita i tugundan oldingir tugunni topsak, i tugun r tugun bilan o„zaro bog„langan tugunlar to„plamidan chiqarib tashlanadi. i= r deb qabul qilinadi va 2- qadamga qaytiladi.




5-qadam (qoldiq tarmoqni topish). N _p {1, k₁ , k₂ ,..., n} to„plam orqali manba tugun (1-tugun)dan to quyilish tugun (n-tugun)gacha bo„lgan yo„l o„tgan tugunlar to„plamni belgilaymiz. U holda ushbu yo„ldan o„tuvchi maksimal oqim quyidagicha hisoblanadi:




f _p min{a₁ , a_k1 , a_{k 2} ,..., a_n }

O„tish yo„lini tashkil etuvchi qirralarning qoldiq o„tkazish qobiliyatlari f _p qiymatga oqim yo„nalishi bo„yicha kamayadi va shuncha miqdorga qarama-qarshi

^сij ^{, с} ji
yo„nalish bo„yicha ko„payadi. Shunday qilib o„tish yo„liga kiruvchi (i,j) qirra

uchun joriy qoldiq qiymatlar quyidagicha o„zgaradi.

1. 
   с_ij f _p , с _ji f _p agar oqim i tugundan j tugunga qarab borayotgan bo„lsa.
   

2. 
   с_ij f _p , с _ji f _p agar oqim j tugundan i tugunga qarab borayotgan bo„lsa
   

Keyinchalik 4-qadamda chetlashtirilgan barcha tugunlar tiklanadi. i=1 deb qabul qilinadi va yangi o„tish yo„lini izlash uchun 2-qadamga qaytiladi.

6-qadam. Yechish

1. 
   topilgan mo„tish yo„llarida maksimal oqim quyidagi formula bo„yicha hisoblanadi
   

F f₁ f₂ ... f_m

2. 
   (i,j) qirraning o„tkazish qobiliyatlarini boshlang„ich ( Cij , C ji ) va yakuniy (oxirgi) ( с_ij , с _ji ) qiymatlariga ega bo„lgan holda ushbu qirradan o„tuvchi optimal
   

oqimni quyidagicha hisoblash mumkin. (										deb qabul qilib,
			, )	(Cij сij , C ji					с ji )
agar	>0 bo„lsa, (i,j) qirra orqali o„tuvchi oqim					ga teng. Agar				0 , bo„lsa, u
holda	oqim	ga teng (bir vaqtning	o„zida			0 va			0	holatda bo„lishi

mumkin emas).

M asala. Quyidagi 32– rasmda ko„rsatilgan tarmoq uchun maksimal oqim hisoblanishi talab etilsin.

32-rasm.
1-iteratsiya

Barcha

qirralarning qoldiq

o„tkazish

qobiliyati cij , c ji

ni

boshlang„ich

o„tkazish qobiliyati

ij ,

ji ga teng deb olamiz.

C

C

1-qadam. a1

qiymat berib, 1-tugunni

,

nishon bilan belgilaymiz

va i 1 deb qabul qilamiz.

2-qadam. S1

2,3,4

.

3-qadam. k

3 , chunki c13

max c12 , c13 , c14

max 20,30,10

30 .

^a3

c13 30

qiymat beramiz va 3-tugunni

30,1

nishon bilan belgilaymiz hamda i 3 deb 2-

qadamga qaytamiz.

2-qadam. S2

4,5 .

3-qadam. k

5 va . a5

^c35

max 10,20

20 .

5-tugunni 20,3

nishon bilan

belgilaymiz. O„tish yo„liga ega bo„lamiz va 5-qadamga o„tamiz.

5-qadam.O„tish yo„lini 1-tugundan boshlab to 5-tugungacha qo„yilgan

nishonlar

bo„yicha topamiz:

5

20,3

3

30,1

1 .

SHunday

qilib

N1 1,3,5

va

f1

min a1 , a3 , a5

,30,20

20

. N1 yo„l bo„ylab qoldiq o„tkazish

qobiliyatini quyidagicha topamiz:

^c13 ^, ^c31

30

20,0

20

10, 20 ,

^c35 ^, ^c53

20

20,0

20

0,20 .

2-iteratsiya
1-qadam. a₁ qiymat berib, 1-tugunni , nishon bilan belgilaymiz va

1. 
   1 deb qabul qilamiz.
   

2-qadam. S₁ 2,3,4 .

3-qadam. k 2 , chunki

nishon bilan belgilaymiz hamda

4-qadam. S₂ 3,5
5-qadam. k 3 va a₃ c₂₃


a₂ c₁₂ max 20,10,10 20 va 2-tugunni 20,1

1. 
   2 deb –qadamga qaytamiz.
   

40 . 3-tugunni 40,2 nishon bilan belgilaymiz.

1. 
   3 deb olib 2-qadamga qaytamiz.
   

2-qadam. S₃ 4 . ( с₃₅ 0 bo„lganligi uchun 5-tugun S₃ ga qiritilmagan)

3-qadam. k	4 va a4	^c34	10 qiymat berib, 4-tugunni 10,3 nishon bilan
belgilaymiz. i 4 deb olib, 2-qadamga qaytamiz.
2-qadam. S4	5 . (1- va 3- tugunlarga nishon qo„yilganligi uchun S4 ga
qiritilmagan).
3-qadam. k	5 va a5	^c45	20 . 5-tugunni			20,4	nishon bilan belgilaymiz.
O„tish yo„liga ega bo„lamiz. 5-qadamga o„tamiz.
5-qadam. N2	1,2,3,4,5 va f2			min	,20,40,10,20 10 . N2 yo„l bo„ylab qoldiq
o„tkazish qobiliyatini hisoblaymiz.
		^c12 ^, ^c21		20	10,0	10	10,10 ,
		^c23 ^, ^c32		40	10,0	10	30,10 ,
		^c34 ^, ^c43		10	10,5	10	0,15 ,
		^c45 ^, ^c54		20	10,0	10	10,10 .