“Floyd algoritmi” mavzusidagi

k-asosiy qadam. k - satr va k - ustunni yetakchi satr va yetakchi ustun sifatida belgilaymiz. D_{k 1} matritsaning barcha d_ij elementlariga uchburchak operatorini qo„llash imkoniyatlarini qarab chiqamiz.

b) Sk matritsani esa Sk 1 matritsadagi sij elementni k ga almashtirish natijasida hosil qilamiz va k k 1 deb olamiz hamda k- qadamni takrorlaymiz.

Algortmning k-qadamidagi faoliyatimizni tushuntirish uchun D_{k 1} matritsani quyidagi rasmda ko„rsatilgandek tasvirlaymiz.

U shbu rasmda k -satr va k -ustunlar yetakchi bo„lsin. i- satr 1 dan to k 1 raqamgacha bo„lgan, r esa k 1dan to n-raqamgacha bo„lgan ixtiyoriy satrlar bo„lsin. Xuddi shuningdek, j-ustun 1 dan to k 1 gacha bo„lgan, g esa k + 1 dan to gacha bo„lgan ixtiyoriy ustun. Uchburchakli operator quyidagicha ishlaydi.

Agar yetakchi satr va ustun elementlari yig„indisi (kvadratiklarda ko„rsatilgan) ular kesishmasida turgan (doiraga olingan) elementdan kichik bo„lsa, masofalar yetakchi elementlar bilan tasvirlangan masofalar yig„indisi bilan almashtiriladi.
Algoritmning n qadami bajarilgandan so„ng D_n va S _n matritsalar bo„yicha i va j tugunlar orasidagi eng qisqa yo„lni topish quyidagi qoida bo„yicha amalga oshiriladi.
1. i va j tugunlar orasidagi masofa D_n matritsada d_ij ga teng.
71

2. i tugundan	j	tugungacha		bo„lgan yo„lda	oraliq	tugunlar S n matritsa
bo„yicha topiladi. Faraz qilaylik,			ij	k , u holda i	kj	yo„lga ega bo„lamiz.
Agar keyinchalik sik	k	va skj	j	bo„lsa, u holda	butun	yo„l aniqlangan deb

hisoblaymiz, chunki barcha oraliq tugunlar topilgan bo„ladi. Aks holda yuqoridagi protsedura i-tugundan k-tugungacha va k-tugundan j-tugungacha bo„lgan yo„llar uchun takrorlanadi.