Internet va axborot kommunikatsiyasi fakulteti

Birinchi qadam
1-cho'qqi minimal yorlig'iga ega.Uning qo'shnilari 2,3 va 6 cho'qqilardir.Biz cho'qqining qo'shnilarini navbat bilan aylanib chiqamiz.
1-cho'qqining birinchi qo'shnisi 2-cho'qqidir, chunki unga boradigan yo'l uzunligi minimaldir. 1-cho'qqi orqali unga boradigan yo'lning uzunligi 1-cho'qqigacha bo'lgan eng qisqa masofa, uning yorlig'i qiymati va 1-dan 2-gacha bo'lgan chekka uzunligi yig'indisiga teng, ya'ni 0 + 7 = 7. Bu 2-cho'qqining joriy yorlig'idan (10000) kamroq, shuning uchun 2-cho'qqining yangi yorlig'i 7 ga teng.

Xuddi shunday, biz boshqa barcha qo'shnilar uchun yo'l uzunligini topamiz (3 va 6 cho'qqilar).
1-vertexning barcha qo'shnilari tekshiriladi. 1-cho'qqigacha bo'lgan joriy minimal masofa yakuniy hisoblanadi va qayta ko'rib chiqilmaydi. 1-cho'qqi tashrif buyurilgan deb belgilangan.
Ikkinchi qadam
Algoritmning 1-bosqichi takrorlanadi. Ko'rilmagan cho'qqilarning "eng yaqinini" yana toping. Bu 7 deb belgilangan cho'qqi 2.
Biz yana tanlangan cho'qqining qo'shnilarining teglarini kamaytirishga harakat qilamiz, ular orqali 2-cho'qqi orqali o'tishga harakat qilamiz. 2-cho'qqining qo'shnilari 1, 3 va 4 cho'qqilaridir.
Vertex 1 allaqachon tashrif buyurilgan. 2-cho'qqining keyingi qo'shnisi 3-vertexdir, chunki u tashrif buyurilmagan deb belgilangan cho'qqilarning minimal yorlig'iga ega. Agar siz unga 2 orqali o'tsangiz, unda bunday yo'lning uzunligi 17 ga teng bo'ladi (7 + 10 = 17). Ammo uchinchi cho'qqining joriy yorlig'i 9 va 9 ni tashkil qiladi< 17, поэтому метка не меняется.

2-cho'qqining yana bir qo'shnisi - 4-vertex. Agar siz unga 2-chi orqali o'tsangiz, bunday yo'lning uzunligi 22 ga teng bo'ladi (7 + 15 = 22). 22 dan beri<10000, устанавливаем метку вершины 4 равной 22.
2-vertexning barcha qo'shnilari ko'rib chiqildi, biz uni tashrif buyurilgan deb belgilaymiz.
Uchinchi qadam
Algoritmning qadamini 3-vertexni tanlab takrorlaymiz.Uni “qayta ishlash”dan keyin quyidagi natijalarga erishamiz.