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

2-nuqtaning barcha qo'shnilari ko'rib chiqildi, biz unga bo'lgan masofani

2-nuqtaning barcha qo'shnilari ko'rib chiqildi, biz unga bo'lgan masofani

muzlatib qo'yamiz va tashrif buyurilgan deb belgilaymiz.

Uchinchi qadam

Algoritmning qadamini 3-nuqtani tanlab takrorlaymiz. Uni “qayta ishlash”dan so‘ng biz quyidagi natijalarni olamiz:

Keyingi qadamlar. Qolgan nuqtalar uchun algoritmning qadamini takrorlaymiz.

Keyingi qadamlar. Qolgan nuqtalar uchun algoritmning qadamini takrorlaymiz.

Bular mos ravishda 6, 4 va 5 uchlari bo'ladi.

Algoritmning bajarilishini yakunlash. Algoritm barcha uchlari kesib tashlangandan keyin tugaydi. Uning ishining natijasi oxirgi rasmda ko'rinadi: 1-2 nuqtagacha bo'lgan eng qisqa yo'l - 7, 3 - 9, 4 - 20, 5 - 20, 6 - 11.

Misol

Rasmda ko'rsatilgan grafik uchun №1 nuqtadan
barcha eng qisqa yo'llarni topish kerak:
https://youtube.com/shorts/XB8D_SF8jCU?feature=share

BERILGAN GRAFIK UCHUN ENG QISQA ARK UZINLIKLARI MATRITSASINI TUZAMIZ.

•  

Eng qisqa yoʻl daraxti quriladigan boshlangʻich choʻqqi 1 choʻqqidir.
Boshlanish shartlarini oʻrnating:
d(1)=0, d(x)=∞ 
Rang berish nuqtasi 1, y=1.

FORMULADAN FOYDALANISH ORQALI BO'YICHA BO'LGAN ENG YAQIN VERTEKSNI TOPAMIZ

d(x)=min{d(x); d(y)+ ay,x}

d(2)=min{d(2);d(1)+a(1,2)}=min{∞;0+10}=10

d(3)=min{d(3);d(1)+a(1,3)}=min{∞;0+18}=18 d(4)=min{d(4);d(1)+a(1,4)}=min{∞;0+8}=8 d(5)=min{d(5);d(1)+a(1,5)}=min{∞;0+∞}=∞ d(6)=min{d(6) ; d(1)+a(1,6)}=min{∞; 0+∞}=∞

1 nuqtadan 4 nuqtagacha bo'lgan yo'l minimal uzunlikka ega d(4)=8. Biz joriy yo'naltirilgan daraxtga №4 nuqtani, shuningdek, ushbu nuqtaga olib boradigan yoyni kiritamiz. Ifodaga ko'ra, bu yoy (1,4)d(2)=min{d(2);d(4)+a(4,2)}=min{10;8+9}=10 d(3)=min{d(3);d(4)+a(4,3)}=min{18;8+∞}=18 d(5)=min{d(5);d(4)+a(4,5)}=min{∞;8+∞}=∞ d(6)=min{d(6) ; d(4)+a(4,6)}=min{∞; 8+12}=20