Deykstra algoritmi Agar barcha balandliklarga tushirilsa algoritm ish faoliyatini to‘xtadi. Aks
holda, tushilmagan balandliklardan eng kichik belgiga ega bo‗lgan u balandlik
tanlanadi. Biz u balandlikning oxiridan oldingi nuqta bo‗lgan barcha bo‗lishi
mumkin marshrutlarni ko‗rib chiqamiz. U balandlikdan qirralar bo`ylab boradigan
balandliklarni balandlikning qo‗shni balandliklari deb ataymiz.
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
