Алогритм Дейкстры

ikkita qo'shnisi 3 va 6-chi bilan bajaramiz.

1-tugunning barcha qo'shnilari tekshiriladi. 1-nuqtagacha bo'lgan joriy

1-tugunning barcha qo'shnilari tekshiriladi. 1-nuqtagacha bo'lgan joriy

minimal masofa yakuniy hisoblanadi va qayta ko'rib chiqilmaydi (bu haqiqatdan ham

shunday ekanligini birinchi marta E. Dijkstra isbotlagan). Ushbu tepaga tashrif

buyurilganligini belgilash uchun uni grafikdan kesib o'ting.

Ikkinchi qadam

Algoritm bosqichi takrorlanadi. Yana biz ko'rilmagan nuqtalarning

"eng yaqinini" topamiz. Bu 7 deb belgilangan 2-nuqta.

Yana biz tanlangan nuqtaning qo'shnilarining teglarini kamaytirishga harakat qilamiz, ular orqali

Yana biz tanlangan nuqtaning qo'shnilarining teglarini kamaytirishga harakat qilamiz, ular orqali

2-nuqta orqali o'tishga harakat qilamiz. nuqta 2 ning qo'shnilari 1, 3 va 4 uchlaridir.2 nuqtasining

birinchi (tartibda) qo'shnisi 1 nuqtadir. Lekin u allaqachon tashrif buyurilgan, shuning uchun

biz 1-nuqta bilan hech narsa qilmaymiz.2-nuqtaning keyingi qo'shnisi 3-nuqtadir,

chunki u kirmagan deb belgilangan nuqtalarning 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 nuqtaning

joriy yorlig'i 9<17 ga teng, shuning uchun yorliq o'zgarmaydi.

2-nuqtaning yana bir qo'shnisi - 4-nuqta. Agar siz unga 2-chi nuqta orqali o'tsangiz, unda bunday yo'lning uzunligi 2-nuqtagacha bo'lgan eng qisqa masofa va 2 va 4 nuqtalar orasidagi masofa yig'indisiga teng bo'ladi, ya'ni. , 22 (7+15=22) . 22<∞ dan boshlab, biz nuqta belgisini 22 ga o'rnatdik.

2-nuqtaning yana bir qo'shnisi - 4-nuqta. Agar siz unga 2-chi nuqta orqali o'tsangiz, unda bunday yo'lning uzunligi 2-nuqtagacha bo'lgan eng qisqa masofa va 2 va 4 nuqtalar orasidagi masofa yig'indisiga teng bo'ladi, ya'ni. , 22 (7+15=22) . 22<∞ dan boshlab, biz nuqta belgisini 22 ga o'rnatdik.