Kommutatsiya va marshrutizatsiya

Ikkinchi qadam
. Algoritm qadami takrorlanadi. Yana biz tushilmagan 
balandliklardan "eng yaqin" balandlikni topamiz. Bu 7 belgiga ega bo‗lgan 2- 
balandlik bo‗ladi. 
7.7- rasm. Deykstra algoritmini 1-balandlikdan 2-balandlikka bo‘yicha grafi 
Yana, biz tanlangan balandlikning qo‗shni balandliklarining belgilarini 
ularga 2-balandlik orqali o‗tish bilan kamaytirishga harakat qilamiz. 2- 
balandlikning qo‗shni balandliklari 1-, 3- va 4- balandliklar bo‗ladi. 
2- balandlikning birinchi qo‗shni balandligi 1-balandlik hisoblanadi. Ammo 
u tushilgan, shuning uchun 1- balandlik bilan hech narsa qilmaymiz. 
2-balandlikning keyingi qo‗shnisi 3- balandlik hisoblanadi, chunki u 
tushilmagan balandliklar sifatida belgilangan balandliklardan minimal belgiga ega. 
Agar unga 2- balandlik orqali o‗tilsa, u holda bunday yo‗lning uzunligi 17 (7 + 10 
= 17) ga teng bo‗ladi. Ammo uchinchi balandlikning joriy belgisii 9 ga teng, bu 17 
dan kichik, shuning uchun belgi o‗zgarmaydi. 
7.8- rasm. Deykstra algoritmini 2-balandlikdan 4-balandlikka o‘tish grafi 

---

52 
2-chi balandlikning yana bir qo‗shnisi 4-chi balandlik hisoblanadi. Agar 
unga 2-chi balandlik orqali o‗tilsa, u holda bu yo‗lning uzunligi 2-chi 
balandlikkacha bo‗lgan eng qisqa masofa va 2-chi va 4-chi balandliklarning 
orasidagi masofaning yig‗indisiga, ya‘ni 22 ga teng bo‗ladi (7 + 15 = 22). 
Binobarin, 4-chi balandlikning belgisini 22 ga teng deb o‗rnatamiz. 
7.9- rasm. Deykstra algoritmini 2-balandlikdan 4-balandlikka o‘tish grafi 

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 

---

53