Samarqand davlat universiteti o. R. Yusupov, I. Q. Ximmatov, E. Sh. Eshonqulov

Download 4,61 Mb. Pdf ko'rish
bet	99/111
Sana	18.05.2024
Hajmi	4,61 Mb.
	#241929

1 ... 95 96 97 98 99 100 101 102 ... 111

Bog'liq
ALGORITMLAR VA MA‟LUMOTLAR STRUKTURALARI

Deykstra algoritmi
keltirilgan.
Dastlabki qadam.
Manbaga (1 belgili uchga)
0
1


qiymatni mos
qo‗yib, bu uchni dastlab


R
deb qabul qilingan
R
to‗plamga kiritamiz:
}
1
{

R
.
R
V
R
\

deb olamiz.
Umumiy qadam.
Boshlangʻich uchi
R
to‗plamga, oxirgi uchi esa
R
to‗plamga tegishli bo‗lgan barcha yoylar to‗plami
)
,
(
R
R
bo‗lsin. Har
bir
)
,
(
)
,
(
R
R
j
i

yoy uchun
ij
i
ij
c
h



miqdorni aniqlaymiz, bu yerda
i

deb
R
i

uchga mos qo‗yilgan qiymat (grafning 1 belgili uchidan chiqib
i
belgili uchigacha eng qisqa yo‗l uzunligi) belgilangan.
ij
R
R
j
i
j
h
)
,
(
)
,
(
min



qiymatni aniqlaymiz.
)
,
(
R
R
to‗plamning oxirgi
tenglikda minimum qiymat beruvchi barcha elementlarini, ya‘ni
)
,
(
j
i
yoylarni ajratamiz. Ajratilgan yoylarning har biridagi
R
j

belgili uchga
j

qiymatni mos qo‗yamiz.
j

qiymat mos qo‗yilgan barcha
j
uchlarni
R
to‗plamdan chiqarib
R
to‗plamga kiritamiz.
Ikkala uchi ham
R
to‗plamga tegishli bo‗lgan barcha
)
,
(
j
i
yoylar
uchun
j
ij
i
c




tengsizlikning
bajarilishini
tekshiramiz.
Tekshirilayotgan tengsizlik o‗rinli bo‗lmagan (ja‘ni
*
*
ij
i
j
c




bo‗lgan)
barcha
*
j
belgili uchlarning har biriga mos qo‗yilgan eski
*
j

qiymat
o‗rniga yangi
*
ij
i
c


qiymatni mos qo‗yamiz va
)
,
(
*
j
i
yoyni ajratamiz.
Bunda eski
*
j

qiymat aniqlangan paytda ajratilgan yoyni ajratilmagan
deb hisoblaymiz.
5
Agar grafda umumiy uzunligi manfiy bo‗lgan sikl mavjud bo‗lsa, u holda grafning qandaydir
s
uchidan shu
siklning biror
i
uchiga o‗tib, keyin esa, sikl bo‗ylab harakatlanib,
i
uchga istalgancha marta qaytish mumkin
bo‗lganligidan, istalgancha kichik uzunlikka ega yo‗l tuzish mumkin.
6
Deykstra Edsger Vayb (Dijkstra Edsger Wybe, 1930-2002) – Gollandiya matematigi.

183
Uchlarga qiymat mos qo‗yish jarayonini oxirgi (
k
belgili) uchga
qiymat mos qo‗yilguncha davom ettiramiz. Grafning 1 belgili uchidan
(manbadan) chiqib uning ixtiyoriy
k
uchigacha (oxirgi uchigacha) eng
qisqa yo‗l uzunligi
k

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
k
uchgacha eng
qisqa uzunlikka ega yo‗l(lar)ni topamiz. ■
1- m i s o l .
2- shaklda tasvirlangan orgrafda oltita uch (
}
6
,
5
,
4
,
3
,
2
,
1
{

V
) va o‗n bitta yoy bo‗lib, har bir yoy uzunligi uning
yoniga yozilgan. Ko‗rinib turibdiki, berilgan grafda manfiy uzunlikka
ega
)
3
,
5
(
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 4,61 Mb.

1 ... 95 96 97 98 99 100 101 102 ... 111

Download 4,61 Mb.

Pdf ko'rish