Birinchi qadam. Bizning misolimiz uchun Deykstra algoritmining qadamini ko’rib chiqamiz. Minimal belgiga 1- balandlik ega. Uning qo’shnilari 2-, 3- va 4- 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 boradigan qirra uzunligi qiymatining yig’indisiga teng, ya‘ni 0 + 6 = 6 bo’ladi. Bu 2-balandlikning joriy belgisidan kichik, shuning uchun 2-nchi balandlikning yangi belgisi 6 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 4- balandliklar bilan bajaramiz, va bizda 3=7, 4=8.
7.5- rasm. Deykstra algoritmini 1-balandlik bo‘yicha hisoblash grafi
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.
Ikkinchi qadam. Algoritm qadami takrorlanadi. Yana biz tushilmagan balandliklardan "eng yaqin" balandlikni topamiz. Bu 6 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- , 4- va 6- balandliklar bo’ladi.
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 10 (6 + 4
= 10) ga teng bo’ladi. Ammo uchinchi balandlikning joriy belgisi 7 ga teng, bu 10 dan kichik, shuning uchun belgi o’zgarmaydi. Bizda 4- balandlik bilan ham huddi shunday amal bajariladi, ya’ni (6+3)>8 bo’lganligi uchun 4- balandlik ham o’zgarishsiz qoldiriladi.
7.8- rasm. Deykstra algoritmini 2-balandlikdan 6-balandlikka o‘tish grafi
2-chi balandlikning yana bir qo’shnisi 6-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 6-chi balandliklarning orasidagi masofaning yig’indisiga, ya‘ni 12 ga teng bo’ladi (6 + 6 = 12). Binobarin, 6-chi balandlikning belgisini 12 ga teng deb o’rnatamiz.
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
|
