Guruh 7- laboratoriya ishi mavzu: marshrutizatsiya algoritmlarini tahlil qilish (deykstra, floyd) Ishdan maqsad

Aliqo’ziyev Diyorbek
412-19 guruh
7- LABORATORIYA ISHI
Mavzu: 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
Birinchi qadam. Bizning misolimiz uchun Deykstra algoritmining qadamini ko‘rib chiqamiz. Minimal belgiga 1- balandlik ega. Uning qo‘shnilari 2-, 3- va 6- balandliklar hisoblanadi.
Navbat bo‘yicha 1-balandlikning birinchi qo‘shnisi 2-balandlik bo‘ladi, chunki ungacha yo‘l uzunligi minimal hisoblanali. Ungacha 1-balandlik orqali yo‘lning uzunligi 1-balandlik belgisi qiymati va 1-balandlikdan 2-balandlikka boradigan qirra uzunligi qiymatining yig‘indisiga teng, ya’ni 0 + 7 = 7 bo‘ladi. Bu 2-balandlikning joriy belgisidan kichik, shuning uchun 2-nchi balandlikning yangi belgisi 7 ga teng bo‘ladi (7.4-rasm).

7.4- rasm. Deykstra algoritmini hisoblash jarayoni

Shunga o‘xshash operatsiyani 1-balandlikning boshqa ikkita qo‘shni balandliklar – 3- va 6- balandliklar bilan bajaramiz.


7.5- rasm. Deykstra algoritmini 1-balandlik bo’yicha hisoblash grafi

1-chi balandlikning barcha qo‘shni balandliklari tekshirildi. 1-balandlikkacha joriy minimal masofa yakuniy hisoblanadi va qayta ko‘rib chiqilmaydi (birinchi marta E. Deykstra shunday ekanligini isbotladi). Bu balandlikka tushilganlikni belgilash uchun uni grafdan o‘chiramiz.

7.6- rasm. Deykstra algoritmini 1-balandlik bo’yicha grafdan o‘chir jarayoni


Xulosa:
Bu labaratoriya ishida men ikkita router orasidagi eng qisqa masofa qancha bo’lishini qonuniyat orqali hisoblab chiqishni ko’rdim, bu ishimda men 6ta qadamda chiqardim.