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

Deykstra algaritmi

Bajardi: Ahmadov Og’abek (105-21 guruh)

Reja:

• 1. Deykstra algaritimi haqida
• 2. Misollar yechish

Algaritm haqida:

Deykstra algoritmi 1959 yilda golland olimi E. Deykstra tomonidan ixtiro

Qilingan grafik algoritmdir. Grafikning bir nuqtasidan (tugun) qolgan barcha

nuqtalarigacha bo'lgan eng qisqa masofani topadi. Algoritm faqat manfiy

qiymatdagi qirralari bo'lmagan grafiklar uchun ishlaydi. Hozirda ushbu

algoritm dasturlash texnologiyalarida va suniy intelektda keng qo'llaniladi

Misol

Rasmda ko'rsatilgan grafik misolida algoritmning bajarilishini ko'rib chiqamiz.
. 1-nuqtadan qolgan barcha nuqtalargacha bo'lgan masofalarni topish talab qilinsin.
Grafikning uchlarni orasidagi chiziqlar ularning masofani (grafikning qirralarini) ko'rsatadi.
Doiralar nuqtalarning raqamlarini ko'rsatadi,
qirralarning tepasida ularning “qiymati" - yo'lning uzunligi ko'rsatilgan.
Har bir nuqta yonida qizil yorliq belgilanadi - bu nuqtaga 1-nuqtagacha
bo'lgan eng qisqa yo'lning uzunligi.

Birinchi qadam

Bizning misolimiz uchun Deykstra algoritmidagi qadamni ko'rib chiqamiz.

1-nuqta minimal qiymatiga ega. 2, 3 va 6 nuqtalar uning qo'shnilaridir.

1-nuqtaning birinchi qo'shnisi o'z navbatida 2-nuqtadir, chunki unga boradigan

1-nuqtaning birinchi qo'shnisi o'z navbatida 2-nuqtadir, chunki unga boradigan

yo'lning uzunligi minimaldir. 1-nuqtai orqali unga boradigan yo'lning uzunligi

1-nuqtagacha bo'lgan eng qisqa masofa, uning qiymati qiymati va 1-dan 2-gacha

bo'lgan nuqta uzunligi yig'indisiga teng, ya'ni 0 + 7 = 7. Bu 2-nuqtaning joriy qiymati,

cheksizlikdan kamroq, shuning uchun 2-nuqtaning yangi qiymati 7 ga teng.

Biz shunga o'xshash operatsiyani 1-nuqtaning boshqa

Biz shunga o'xshash operatsiyani 1-nuqtaning boshqa