|
Kommutatsiya va marshrutizatsiyaBog'liq Kommutatsiya va marshrutizatsiya (1-qism)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
|
| |
