48
7- LABORATORIYA 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.
