7- amaliy mashg’ulot ishi

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