22-ma’ruza. Eng qisqa yo’lni topish algoritmlari (2 soat). Reja



Download 413,55 Kb.
bet5/9
Sana23.07.2022
Hajmi413,55 Kb.
#844300
1   2   3   4   5   6   7   8   9
Bog'liq
Eng qisqa yo’lni topish algoritmlari

22.3. Deykstra algoritmi.

Minimal uzuznlikka ega yo‘l haqidagi masalani hal etish usullari orasida Deykstra tomonidan taklif etilgan algoritm ko‘p qo‘llaniladi. Quyida grafning 1 belgili uchidan chiqib (bu uchni manba deb qabul qilamiz) grafdagi ixtiyoriy uchgacha (bu uchni oxirgi uch deb hisoblaymiz) eng qisqa uzunlikka ega yo‘lni topish imkonini beruvchi Deykstra algoritmi keltirilgan.


Dastlabki qadam. Manbaga (1 belgili uchga) qiymatni mos qo‘yib, bu uchni dastlab deb qabul qilingan to‘plamga kiritamiz: . deb olamiz.
Umumiy qadam.Boshlang‘ich uchi to‘plamga, oxirgi uchi esa to‘plamga tegishli bo‘lgan barcha yoylar to‘plami bo‘lsin. Har bir yoy uchun miqdorni aniqlaymiz, bu yerda deb uchga mos qo‘yilgan qiymat (grafning 1 belgili uchidan chiqib belgili uchigacha eng qisqa yo‘l uzunligi) belgilangan.
qiymatni aniqlaymiz. to‘plamning oxirgi tenglikda minimum qiymat beruvchi barcha elementlarini, ya’ni yoylarni ajratamiz. Ajratilgan yoylarning har biridagi belgili uchga qiymatni mos qo‘yamiz. qiymat mos qo‘yilgan barcha uchlarni to‘plamdan chiqarib to‘plamga kiritamiz.
Ikkala uchi ham to‘plamga tegishli bo‘lgan barcha yoylar uchun tengsizlikning bajarilishini tekshiramiz. Tekshirilayotgan tengsizlik o‘rinli bo‘lmagan (ja’ni bo‘lgan) barcha belgili uchlarning har biriga mos qo‘yilgan eski qiymat o‘rniga yangi qiymatni mos qo‘yamiz va yoyni ajratamiz. Bunda eski qiymat aniqlangan paytda ajratilgan yoyni ajratilmagan deb hisoblaymiz.
Uchlarga qiymat mos qo‘yish jarayonini oxirgi ( belgili) uchga qiymat mos qo‘yilguncha davom ettiramiz. Grafning 1 belgili uchidan (manbadan) chiqib uning ixtiyoriy uchigacha (oxirgi uchigacha) eng qisqa yo‘luzunligi bo‘ladi.
Oxirgi qadam. Grafning oxirgi uchidan boshlab ajratilgan yoylar yo‘nalishiga qarama-qarshi yo‘nalishda uning 1 belgili uchiga kelguncha harakatlanib, natijada grafdagi 1 belgili uchdan ixtiyoriy uchgacha eng qisqa uzunlikka ega yo‘l(lar)ni topamiz.

2- misol. 2- shaklda tasvirlangan orgrafda oltita uch ( ) va o‘n bitta yoy bo‘lib, har bir yoy uzunligi uning yoniga yozilgan. Ko‘rinib turibdiki, berilgan grafda manfiy uzunlikka ega yoy ham bor. Isbotlash mumkinki, bu grafda umumiy uzunligi manfiy bo‘lgan sikl mavjud emas.
Yuqorida bayon qilingan Deykstra algoritmini berilgan grafga qo‘llab, eng qisqa uzunlikka ega yo‘lni topish bilan shug‘ullanamiz.

Download 413,55 Kb.

Do'stlaringiz bilan baham:
1   2   3   4   5   6   7   8   9




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish