Oxirgi qadam. Berilgan orgrafda 1 belgili uchdan 6 belgili uchgacha eng qisqa uzunlikka ega yo‘l(lar)ni topish maqsadida,
algoritmga asosan, grafning oxirgi 6 belgili uchidan boshlab ajratilgan yoylar yo‘nalishiga qarama-qarshi yo‘nalishda harakatlanib, uning 1 belgili uchiga kelishimiz kerak. 6 belgili uchga kiruvchi uchta yoydan
faqat bittasi ( (4, 6)
yoy) ajratilgan bo‘lgani uchun
(4, 6)
yoy yo‘nalishiga
qarama-qarshi yo‘nalishda harakat qilib, 6 belgili uchdan 4 belgili
uchga kelamiz. 4 belgili uchga kiruvchi ikkala ( (1, 4) va (3, 4) ) yoylar
ham ajratilgan bo‘lgani uchun biz tuzmoqchi bo‘lgan eng qisqa uzunlikka ega yo‘l yagona emas.
algoritmga asosan, grafning oxirgi 6 belgili uchidan boshlab ajratilgan yoylar yo‘nalishiga qarama-qarshi yo‘nalishda harakatlanib, uning 1 belgili uchiga kelishimiz kerak. 6 belgili uchga kiruvchi uchta yoydan
faqat bittasi ( (4, 6)
yoy) ajratilgan bo‘lgani uchun
(4, 6)
yoy yo‘nalishiga
qarama-qarshi yo‘nalishda harakat qilib, 6 belgili uchdan 4 belgili
uchga kelamiz. 4 belgili uchga kiruvchi ikkala ( (1, 4) va (3, 4) ) yoylar
ham ajratilgan bo‘lgani uchun biz tuzmoqchi bo‘lgan eng qisqa uzunlikka ega yo‘l yagona emas.
Agar harakatni
(1, 4)
yoy yo‘nalishiga teskari yo‘nalishda davom
ettirsak, u holda 4 belgili uchdan 1 belgili uchga kelib, eng qisqa
uzunlikka ega yo‘llardan biri bo‘lgan
1 (1, 4, 6)
marshrutni topamiz.
Agarda harakatni
(3, 4)
yoy yo‘nalishiga teskari yo‘nalishda davom
ettirsak, u holda 4 belgili uchdan 3 belgili uchga kelamiz. 3 belgili
uchga kiruvchi ikkita yoydan faqat bittasi ( (5, 3) yoy) ajratilgan bo‘lgani
uchun 3 belgili uchdan 5 belgili uchga kelamiz. Shu usulda davom etsak, oldin 2 belgili, keyin esa 1 belgili uchga o‘tib mumkin bo‘lgan eng qisqa uzunlikka ega bo‘lgan yo‘llardan ikkinchisini, ya’ni
2 (1, 2, 5, 3, 4, 6) marshrutni aniqlaymiz.
Shunday qilib, 2- shaklda tasvirlangan grafda eng qisqa uzunlikka
|
