7- amaliy mashg’ulot ishi

Uchinchi qadam. 3-chi balandlikni tanlash bilan algoritmning qadamini takrorlaymiz. Unga "ishlov berish"dan so’ng quyidagi natijalarni olamiz:

7.11- rasm. Deykstra algoritmini 3-balandlik bo‘yicha hisoblash grafi

Keyingi qadamlar. Qolgan balandliklar uchun algoritmning qadamini takrorlaymiz. Bu mos ravishda 6-, 4- va 5-nchi balandliklar bo’ladi.

7.12- rasm. Deykstra algoritmini 6-, 4- va 5-nchi balandliklar bo‘yicha o‘tish grafi

Algoritmni bajarilishini tugatish. Algoritm hech bir balandlikka ishlov berish mumkin bo’lmaganda ishlashni tugatadi. Bu misolda barcha balandliklar o’chirilgan, ammo har qanday misolda ham shunday bo’ladi deb faraz qilish xato bo’ladi, ayrim balandliklar, agar ularga yetib borish imkoni bo’lmasa, o’chirilmay qolishi mumkin. Algoritmning natijasi oxirgi rasmdan ko’rinadi: 1-nchi balandlikdan 2-chi balandlikkacha bo’lgan eng qisqa yo’l 7 ni, 3-chi balandlikkacha yo’l – 9 ni, 4-chi balandlikkacha yo’l – 20 ni, 5-chi balandlikkacha yo’l – 20 ni, 6-chi balandlikkacha yo’l 11 ni tashkil etadi.

Жараён	Belgi	1	2	3	4	5	6	7	8	9
0	L	0	∞	∞	∞	∞	∞	∞	∞	∞
	Q
1	L	0	9	2	7	∞	∞	∞	∞	∞
	Q		1	1	1
2	L	0	9	2	7	∞	8	7	∞	∞
	Q		1	1	1		3	3
3	L	0	9	2	7	∞	8	7	23	∞
	Q		1	1	1		3	3	7
4	L	0	9	2	7	22	8	7	23	∞
	Q		1	1	1	4	3	3	7
5	L	0	9	2	7	11	8	7	20	22
	Q		1	1	1	6	3	3	6	6
6	L	0	9	2	7	11	8	7	20	22
	Q		1	1	1	6	3	3	6	6
7	L	0	9	2	7	11	8	7	20	21
	Q		1	1	1	6	3	3	6	5
8	L	0	9	2	7	11	8	7	20	21
	Q		1	1	1	6	3	3	6	5

FLOYD ALGORITMINING ISHLASH PRINSIPINI TADQIQ QILISH

Nazariy ma’lumotlar
Floyd algoritmi - yo’naltirilgan grafning barcha balandliklari orasidagi eng qisqa masofani topish uchun dinamik algoritm hisoblanadi. U 1962 yilda Robert Floyd tomonidan ishlab chiqilgan, 1959 yilda Bernard Roy (Bernard Roy) xuddi shu algoritmni e‘lon qilgan bo’lsa-da, ammo bu ahamiyatsiz bo’lib qoldi.
Bu algoritm Deykstra algoritmiga qaraganda umumiyroq hisoblanadi, chunki u istalgan ikkita tarmoq qurilma orasidagi eng qisqa yo’llarni topadi. Bu algoritmda tarmoq n satrlar va n ustunlarga ega bo’lgan kvadrat matritsa shaklida berilgan. (i, j) element i tugundan ј tugungacha bo’lgan d_ij masofaga teng, u agar (i, j) joy mavjud bo’lsa, chekli qiymatga ega va aks holda cheksizlikka teng bo’ladi.
Oldin Floyd usulining asosiy g’oyasini ko’rsatamiz. Aytaylik, uchta i , j va k tugunlar mavjud va ular orasidagi masofalar berilgan (8.1-rasm). Agar d_ij + d_jk ik tengsizlik bajarilsa, u holda i → k yo’lni i → ј → k bilan almashtirish tavsiya etiladi. Bunday almashtirish (bundan keyin uni shartli ravishda uchburchak operator deb ataymiz) Floyd algoritmini bajarish jarayonida muntazam ravishda amalga oshiriladi.
7.12-rasm. Uchburchak operatori
Floyd algoritmi quyidagi amallarni bajarilishini talab qiladi.
0-qadam. Dastlabki D₀ masofa matritsasi va S₀ tugunlarning ketma-ketlik matritsasini aniqlaymiz. Ikkala matritsaning diagonal elementlari "-" belgisi bilan
belgilanadi. U bu elementlarni hisoblashlarda qatnashmasligini ko’rsatadi. k = 1 deb olamiz:

7.13-rasm. Floyd algoritmi bo‘yicha dastlabki holat
Asosiy k-qadam. Yetakchi satr va yetakchi ustun sifatida k satr va k ustunni beramiz. Uchburchak operatorni D_k-1 matritsaning barcha d_ij elementlariga qo’llash imkoniyatini ko’rib chiqamiz. Agar d_ik + d_kj < d_ij, (i<>k, j<>k, i<>j) tengsizlik bajarilsa, quyidagi amallarni bajaramiz:

• 
  D_k-1 matritsadagi d_ij elementni d_ik + d_kj yig’indi bilan almashtirish orqali D_k matritsani hosil qilamiz;
  
• 
  S_k-1 matritsadagi s_ij elementni k ga almashtirish orqali S_k matrisani hosil qilamiz.
  

k = k + 1 o’rnatamiz va k qadamni takrorlaymiz.
8.3-rasmda tasvirlanganidek, D_k-1 matritsani taqdim qilish orqali algoritmning k-nchi qadamida bajarilgan amallarni tushuntiramiz. Bu rasmda k satr
va k ustun yetakchi hisoblanadi. i satr 1 dan k - 1 gacha bo’lgan istalgan satr, r satr esa k + 1 dan n gacha bo’lgan raqamli istalgan satr hisoblanadi. Xuddi shunday tarzda ј ustun 1 dan k - 1 gacha bo’lgan istalgan ustunni anglatadi, q ustun k + 1 dan n gacha bo’lgan raqamli istalgan ustun hisoblanadi.

.

7.14- rasm. Floyd algoritmini tasvirlash
Uchburchak operatori quyidagicha amalga oshiriladi. Agar yetakchi satr va ustun elementlarining yig’indisi (kvadratlarda ko’rsatilgan) qaralayotgan yetakchi elementlarga mos keladigan ustun va satrning kesishmasida joylashgan elementlardan (doiralarda ko’rsatilgan) kichik bo’lsa, u holda masofa (doiradagi element) yetakchi elementlar orqali ko’rsatilgan masofalar yig’indisi bilan almashtiriladi (8.3- rasm).
Algoritmning n qadamlari bajarilgandan keyin D_n va S_n matritsalar bo’ycha i va ј tugunlar orasidagi eng qisqa yo’lni aniqlash quyidagi qoidalar bo’yicha amalga oshiriladi.
i va ј tugunlari orasidagi masofa D_n matritsadagi d_ij elementga teng.
i tugundan ј tugungacha bo’lgan yo’ldagi oraliq tugunlar S_n matritsa bo’yicha aniqlanadi. s_ij = k bo’lsin, u holda i→ k → ј yo’lga ega bo’lamiz. Agar
s_ik = k va s_kj = ј bo’lsa, u holda barcha oraliq tugunlar topilganligi sababli, butun yo’l aniqlangan deb faraz qilamiz. Aks holda, ј tugundan k tugunga va k tugundan ј tugungacha bo’lgan yo’llar uchun tavsiflangan protsedurani takrorlaymiz.
Misol. 8.4-rasmda tasvirlangan tarmoq uchun istalgan ikkita tugunlar orasidagi eng qisqa yo’llarni topamiz. Bu tarmoqning tugunlari orasidagi masofa 8.4-rasmda mos qirralarning yaqinidagi qo’yilgan. (3, 5) qirra yo’naltirilgan, shuning uchun 5-nchi tugundan 3-nchi tugungacha harakatlanish mumkin emas. Qolgan barcha qirralar har ikkala tomonlarga harakatlanishga ruxsat etadi (8.4- rasm).
7.15- rasm. Floyd algoritmi uchun tarmoq tuzilishi

0. 
   qadam. Dastlabki D₀ va S₀ matritsalar to’g’ridan-to’g’ri berilgan tarmoq sxemasiga binoan quriladi. D₀ matritsa d₃₅ va d₅₃ elementlar juftligidan tashqari, nosimmetrik hisoblanadi, bu yerda d₅₃ cheksizlikka teng, chunki 5-nchi tugundan 3-nchi tugunga o’tish mumkin emas:
   

7.16-rasm. Berilgan tarmoq grafi uchun dastlabki holatlar matritsalari

0. 
   qadam. D₀ matritsada yetakchi satr va ustun (k = 1) tanlangan. Juft ramka bilan d₂₃ va d₃₂ elementlar ajratilgan, ular qiymatlarini uchburchak operator orqali
   

yaxshilash mumkin bo’lgan D₀ matritsa elementlari orasida yagona elementlar hisoblanadi. Shunday qilib, D₀ va S₀ matritsalar asosida D₁ va S₁ matritsalarni olish uchun quyidagi amallarni bajaramiz.
d₂₃ ni d₂₁ + d₁₃ = 3 + 10 = 13 bilan almashtiramiz va s₂₃ = 1 ni o’rnatamiz. d₃₂ ni d₃₁ + d₁₂ = 10 + 3 = 13 bilan almashtiramiz va s₃₂ = 1 ni o’rnatamiz. D₁ va S₁ matritsalar quyidagi shaklga ega:

7.17-rasm. D₁ va S₁ matritsalari

0. 
   qadam. k = 2 deb olamiz; D₁ matritsada yetakchi satr va ustun ajratilgan. Uchburchak operator juft ramka bilan ajratilgan D₁ va S₁ matritsalar elementlariga qo’llaniladi. Natijada D₂ va S₂ matritsalarini olamiz:
   

7.18-rasm. D₂ va S₂ matritsalar

0. 
   qadam. k = 3 deb olamiz; D₂ matritsada yetakchi satr va ustun ajratilgan. Uchburchak operator juft ramka bilan ajratilgan D₂ va S₂ matritsalar elementlariga qo’llaniladi. Natijada D₃ va S₃ matritsalarni olamiz:
   

7.19-rasm. D₃ va S₃ matritsalar

0. 
   qadam. k = 4 deb olamiz, D₃ matritsada yetakchi satr va ustun ajratilgan.
   

D₄ va S₄ yangi matritsalarni olamiz:

7.20-rasm. D₄ va S₄ matritsalari

0. 
   qadam. k = 5 olamiz, D₄ matritsadagi yetakchi satr va ustun ajratilgan. Bu qadamda hech qanday amallarni bajarmaymiz; hisoblashlar yakunlandi.
   

D₄ va S₄ yakuniy matritsalar istalgan tarmoqning ikkita tugunlari orasidagi eng qisqa yo’llarni aniqlash uchun zarur bo’ladigan barcha ma‘lumotlarni o’z ichiga oladi. Masalan, 1- va 5-nchi tugunlar orasidagi eng qisqa masofa d₁₅ = 12 ga teng bo’ladi.
Mos marshrutlarni topish uchun marshrutning ta‘kidlaymizki, (i, j) segment faqat s_ij = j bo’lganda (i, j) qirradan iborat bo’ladi. Aks holda, i va ј tugunlar kamida bitta oraliq tugun orqali ulanadi. Masalan, s₁₅ = 4 va s₄₅ = 5 bo’lganligi sababli, avval 1 va 5 tugunlar orasidagi eng qisqa yo’l 1→ 4 → 5 bo’ladi. Ammo s₁₄ 4 ga teng emasligi sababli, 1 va 4 tugunlar ma‘lum bir yo’lda bitta qirra bilan
ulanmagan (lekin dastlabki tarmoqda ular to’g’ridan-to’g’ri bog’langan bo’lishi mumkin).
Keyin 1 va 4 - tugunlar orasidagi oraliq tugunlarni aniqlash kerak bo’ladi. s₁₄
= 2 va s₂₄ = 4 ga egamiz, shuning uchun 1→4 marshrutni 1→ 2→ 4 marshrut bilan almashtiramiz. s₁₂ = 2 va s₂₄ = 4 bo’lganligi sababli, boshqa oraliq tugunlar mavjud emas. Marshrutning ma‘lum segmentlarini birlashtirish bilan nihoyat 1 tugundan 5 tugungacha bo’lgan eng qisqa yo’l - 1→ 2→ 4→ 5 ni olamiz. Bu yo’lning uzunligi 12 kilometrga teng.


Topshiriq. Birinchi va oxirgi tugunlar o’rtasida eng qisqa marshrutni Deysktra va Floyd algoritmlari yordamida aniqlang

№1		№2
№3		№4
№5		№6
№7		№8
№9		№10

№11		№12
№13		№14
№15		№16
№17		№18
№19		№20
№21		№22
№23		№24
№25		№26

№27		№28
№29		№30

Nazorat savollari

1. 
   Marshrutizatsiya deganda nimani tushunasiz ?
   
2. 
   Qanday turdagi marshrutizatsiya protokollarini bilasiz ?
   
3. 
   Qanday turdagi marshrutizatsiya algoritmlarini bilasiz. ?
   
4. 
   Eng qisqa marshrut tarmoqning qaysi ko`rsatkichlarini o’z ichiga oladi?
   
5. 
   Marshrut metrikasi deganda nimani tushunasiz?