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 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.
7.6- rasm. Deykstra algoritmini 1-balandlik bo’yicha grafdan o‘chir jarayoni
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
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
| 