Kommutatsiya va marshrutizatsiya

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

Keyingi qadamlar. Qolgan balandliklar uchun algoritmning qadamini takrorlaymiz. Bu mos ravishda 6-, 4- va 5-nchi balandliklar bo‘ladi.

7.12- rasm. Deykstra algoritmini 6-, 4- va 5-nchi balandliklar bo’yicha o’tish grafi