Kommutatsiya va marshrutizatsiya

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.
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 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