|
Raqamli texnologiyalari vazirligi muhammad al-xorazmiy nomidagi
|
bet | 1/2 | Sana | 14.03.2024 | Hajmi | 115.76 Kb. | | #171931 |
Bog'liq 7yPoc8uoKsyKt8mcv9P1, 1703098601, 1. Multimedia axborot oqimlar. Multimedia trafikning asosiy para, CamScanner 03-15-2024 17.08, sug\'urta, 7-lab2
O‘ZBEKISTON RESPUBLIKASI
RAQAMLI TEXNOLOGIYALARI VAZIRLIGI
MUHAMMAD AL-XORAZMIY NOMIDAGI
TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI
Telekommunikatsiya texnologiyalari fakulteti
411-20 guruh talabasining
Mustaqil ishi
“Kommutatsiya va marshrutizatsiya” fanidan
DEYKSTRA MARSHRUTIZATSIYA ALGORITMINI TAHLIL QILISH
Bajardi: Yakubjonov Fazliddin
Tekshirdi: Qodirov Azamat
Toshkent 2023
DEYKSTRA MARSHRUTIZATSIYA ALGORITMINI TAHLIL QILISH Mustaqil ishdan maqsad: Ma’lumot uzatish tarmoqlarida qo‘llaniluvchi Deykstra marshrutizatsiya algoritmining ishlash tamoyilini tahlil qilish va ko‘nikmaga ega bo’lish.
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 toplamdan 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.
|
| |