49
U balandlikning tushilmagan balandliklardan tashqari, har bir qo‗shni
balandligi uchun joriy belgi va u balandlikning bu balandlik bilan bog‗laydigan
qirraning uzunligi qiymatlari yig‗indisi teng bo‗lgan yangi yo‗lning
uzunligini
hisoblaymiz.
Agar olingan uzunlik qiymati qo‗shni balandlik belgisining qiymatidan
kichik bo‗lsa, belgi qiymatini olingan uzunlik qiymati bilan almashtiramiz. Barcha
qo‗shni balandliklarni ko‗rib chiqish bilan u balandlikni
tushilgan sifatda
belgilaymiz va algoritm qadamini takrorlaymiz.
7.1-rasmda ko‗rsatilgan graf misolida algoritmning bajarilishini ko‗rib
chiqamiz. 1-chi balandlikdan qolgan barcha balandliklargacha eng qisqa masofani
topish talab qilinadi.
Doiralar bilan balandliklar, liniyalar bilan esa ularning orasidagi yo‗llar (graf
qirralarini) belgilanadi. Doiralarda
balandliklarning raqamlari, qirralarning ustida
ularning "narxi" - yo‗l uzunligi belgilanadi. Har bir balandlikning yonidagi belgi -
bu balandlikdan 1-chi balandlikkacha bo‗lgan eng qisqa yo‗lning
uzunligi qizil
rang bilan belgilanadi.
a)
b)
c)
7.1- rasm. Deykstra algoritmini hisoblash qadamlari (a,b,c)
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
50
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.
51
7.6- rasm. Deykstra algoritmini 1-balandlik bo‘yicha grafdan o‗chir jarayoni
