7- amaliy mashg’ulot ishi

7- AMALIY MASHG’ULOT ISHI

MARSHRUTIZATSIYA ALGORITMLARINI TAHLIL QILISH (DEYKSTRA, FLOYD)


Ishdan maqsad: Ma‘lumot uzatish tarmoqlarida qo’llaniluvchi marshrutizatsiya algoritmining ishlash tamoyilini tahlil qilish va ko`nikmaga ega bo‘lish.

Nazariy ma’lumotlar

Deykstra algoritmi bo`lib, 1959 yilda gollandiyalik olim E. Deykstra tomonidan ixtiro qilingan. Grafning bitta balandligidan boshqa balandliklarigacha eng qisqa yo’llarni topadi. Algoritm faqat manfiy vaznsiz graflar uchun ishlaydi. Algoritm dasturlashda va texnologiyalarda keng qo’llaniladi, masalan, u OSPF va IS-IS marshrutizatsiya protokollarida ishlatiladi.
V to’plamdan har bir balandlikka biz belgini biriktiramiz, bu balandlikdan A balandlikkacha ma‘lum minimal masofa bo’ladi. Algoritm qadam-baqadam ishlaydi, har bir qadamda bitta balandlikka "tushadi" va belgilarni kamaytirishga xarakat qiladi. Algoritm barcha balandliklarga tushganda tugaydi.
Initsializatsiyalash. A balandlikni o’zining belgisi 0 ga teng deb olinadi, qolgan balandliklarining belgilari cheksiz olinadi. Bu A balandlikdan boshqa balandliklargacha bo’lgan masofalar hali noma‘lum ekanligidan dalolat beradi. Grafning barcha balandliklari tushilmagan deb belgilangan.

Deykstra algoritmi

Agar barcha balandliklarga tushirilsa algoritm ish faoliyatini to‘xtadi. Aks holda, tushilmagan balandliklardan eng kichik belgiga ega bo’lgan u balandlik tanlanadi. Biz u balandlikning oxiridan oldingi nuqta bo’lgan barcha bo’lishi mumkin marshrutlarni ko’rib chiqamiz. U balandlikdan qirralar bo`ylab boradigan balandliklarni balandlikning qo’shni balandliklari deb ataymiz.
U balandlikning tushilmagan balandliklardan tashqari, har bir qo’shni balandligi uchun joriy belgi va u balandlikning bu balandlik bilan bog’laydigan qirraning uzunligi qiymatlari yig’indisi teng bo’lgan yangi yo’lning uzunligini hisoblaymiz.
Agar olingan uzunlik qiymati qo’shni balandlik belgisining qiymatidan kichik bo’lsa, belgi qiymatini olingan uzunlik qiymati bilan almashtiramiz. Barcha qo’shni balandliklarni ko’rib chiqish bilan u balandlikni tushilgan sifatda belgilaymiz va algoritm qadamini takrorlaymiz.
7.1-rasmda ko’rsatilgan graf misolida algoritmning bajarilishini ko’rib chiqamiz. 1-chi balandlikdan qolgan barcha balandliklargacha eng qisqa masofani topish talab qilinadi.
Doiralar bilan balandliklar, liniyalar bilan esa ularning orasidagi yo’llar (graf qirralarini) belgilanadi. Doiralarda balandliklarning raqamlari, qirralarning ustida ularning "narxi" - yo’l uzunligi belgilanadi. Har bir balandlikning yonidagi belgi - bu balandlikdan 1-chi balandlikkacha bo’lgan eng qisqa yo’lning uzunligi qizil rang bilan belgilanadi.

1. 
   b) c) 7.1- rasm. Deykstra algoritmini hisoblash qadamlari (a,b,c)