19. Прима-Дeйкстра алгoритми. Вақт бўйича самарадoрлигини баҳoлаш


Dijkstraning eng qisqa yo'l algoritmi | Ochko'z Algo-7



Download 140,24 Kb.
bet4/7
Sana13.04.2021
Hajmi140,24 Kb.
#63261
1   2   3   4   5   6   7
Bog'liq
AL JT mustaqil ish

Dijkstraning eng qisqa yo'l algoritmi | Ochko'z Algo-7


Grafikadagi manba va vertexni berilgan holda, berilgan grafikdagi manbadan vertikalgacha bo'lgan eng qisqa yo'llarni toping.

Dijkstraning algoritmi Primning minimal daraxtni qisqartirish algoritmiga juda o'xshaydi . Prim's MST singari, biz ildiz sifatida berilgan manbaga ega bo'lgan SPT (eng qisqa yo'l daraxti) yaratamiz. Biz ikkita to'plamni saqlaymiz, bitta to'plamda eng qisqa yo'l daraxtiga kiritilgan uchlari bor, boshqa to'plamda hali eng qisqa yo'l daraxtiga kiritilmagan uchlari mavjud. Algoritmning har bir bosqichida biz boshqa to'plamda joylashgan (hali kiritilmagan to'plam) va manbadan minimal masofaga ega bo'lgan verteksni topamiz.

Quyida Dijkstra algoritmida bitta manbali vertexdan berilgan grafikning barcha boshqa uchlariga eng qisqa yo'lni topish uchun foydalanilgan batafsil qadamlar keltirilgan.
Algoritm
1) Qisqa yo'l daraxti tarkibiga kiritilgan, ya'ni manbadan minimal masofa hisoblab chiqilgan va oxiriga etkaziladigan sptSet (qisqa daraxtlar to'plami) to'plamini yarating . Dastlab, ushbu to'plam bo'sh.
2) Kirish grafigidagi barcha uchlarga masofa qiymatini bering. Barcha masofa qiymatlarini INFINITE sifatida boshlang. Manba cho'qqisi uchun masofa qiymatini 0 sifatida belgilang, shunda u avval tanlanadi.


Download 140,24 Kb.

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




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