Deykstra Algoritmi
![Mavzu: Deykstra Algoritmi.
MUNDARIJA
KIRISH .......................................................................................................................................................................................
1.Graflar nazariyasining asosiy tushunchalari ..........................................................................................................................
2.Deykstra algoritmining paydo bo’lishi ...................................................................................................................................
3.Deykstra Algoritmi ................................................................................................................................................................
4. Eng qisqa yo’llar masalalarining turlari ..............................................................................................................................
5.Deykstra algoritmning so’zli tavsifi ......................................................................................................................................
6.Deykstra algoritmning C++ da kodi .....................................................................................................................................
7.Tegishli muammolar va algoritmlar .....................................................................................................................................
Xulosa ....................................................................................................................................................................................
Foydalangan adabiyotlar: .......................................................................................................................................................](/data/documents/b731630c-7286-47f1-bfc3-5300c55023a9/page_1.png)
![KIRISH
Qandaydir masalani xal etishga kirishishdan avval buning uchun eng
yaxshi uslub izlanadi va uni qay tarzda tavsiflash aniqlanadi . Boshqacha qilib
aytganda , biz doimo maqsadi ba ’ zi bir zaruriy natijaga erishishdan iborat ,
amallar ketma - ketligi bilan berilgan turli - tuman qoidalarga duch kelamiz .
Bunday amallarning ketma - ketligi algoritm deb ataymiz .
Matematikada algoritmning murakkabligi , xal etish masalalari va ularni
ishlab chiqish prinsiplarini o ’ rganadigan maxsus “ Algoritmlar nazariyasi ”
bo ’ limi xam mavjud .
Algoritmlar nazariyasi – algoritmlarning umumiy xossalari , qonuniyatlari
va ularni tasvirlanishining turli - tuman formal modellarini o ’ rganish bilan
shug ’ ullanadi . Algoritm tushunchasini formallashtirish asosida ularning
samaradorligi taqqoslash, ularning ekvivalentligi tekshirish, qo’llanilish sohasini
aniqlash mumkin.
Algoritm – berilgan natijaga erishish uchun qilinishi kerak bo lgan aniqʻ
ko rsatmalar ketma-ketligi. Algoritm keng ma noda faqat kompyuterga oid
ʻ ʼ
atama bo’lmay, balki unda berilgan ko rsatmalarni bajara oluvchi har qanday
ʻ
narsaga oiddir.
Algoritm, algoritm – ma lum bir turga oid masalalarni yechishda
ʼ
ishlatiladigan amallarning muayyan tartibda bajarilishi haqidagi aniq qoida
(dastur). Kibernetika va matematikaning asosiy tushunchalaridan biri. O rta
ʻ
asrlarda o nli sanoq tizimi bo yicha to rt arifmetik amal bajariladigan qoidani
ʻ ʻ ʻ
Algaritm deb atashgan. "Bu qoidalarni matematikaga 9-asrda al-Xorazmiy
tomonidan kiritilgan.](/data/documents/b731630c-7286-47f1-bfc3-5300c55023a9/page_2.png)
![Ushbu kurs ishida biz graflar nima va Dijkstra algoritmi nima ekanligini
o’rganamiz. Keyinchalik, biz Dijkstra algoritmi va uning c++ kodi misolini,
tegishli chiqishi bilan birga o’rganamiz. Shuningdek, biz ushbu algoritmning
real dunyoda amaliy qo’llanilishini yanada chuqurroq o’rganamiz. Shunday
ekan, boshlaylik!
1.Graflar nazariyasining asosiy tushunchalari
Graflar chiziqli bo’lmagan ma’lumotlar strukturasi bo’lib, u tugunlar va
qirralarni o’z ichiga oladi. Tugunlar - bu cho’qqilar va qirralar - graflardagi
ikkita tugunni bog’laydigan chiziqlar. Shuning uchun, graflarni tugunlarni
bog’laydigan cho’qqilar to’plami va qirralarning to’plami sifatida aniqlash
mumkin. Agar biz Facebook-ni graf deb hisoblasak, unda Facebook-dagi
odamlar to’plami tugunlar deb hisoblanadi va ular orasidagi bog’liqlik chekkalar
sifatida ko’rib chiqilishi mumkin. Shuning uchun, graflar elementlar juftligi
orasidagi "bog’lanish" ni ko’rsatish uchun ishlatiladigan ma’lumotlar
tuzilmalari. Quyidagi rasmda graflarning grafik tasviri ko’rsatilgan.
Qirralari va uchlari bo’lgan grafga misol
Umuman olganda, ikkita turdagi graflar mavjud:
Yo’naltirilmagan graf: Yo’naltirilmagan grafdan foydalanib, har bir bog’langan
tugun juftligi uchun siz bir tugundan ikkinchisiga har ikki yo’nalishda ham
o’tishingiz mumkin. Uchlar Qirra](/data/documents/b731630c-7286-47f1-bfc3-5300c55023a9/page_3.png)
![Yo’naltirilgan graf: Yo’naltirilgan graf yordamida siz har bir bog’langan tugun
juftligi uchun faqat ma’lum bir yo’nalishda bir tugundan ikkinchisiga o’tishingiz
mumkin. Ikki tugunni birlashtiruvchi chekka sifatida o’qlardan foydalanishingiz
mumkin.
Bundan tashqari, vaznli graf - bu o’ziga xos "og’irlik" yoki "xarajat" ga ega
bo’lgan qirralardan tashkil topgan graf. Biron bir og’irligini, vaqtni, masofani
yoki juftlik tugunlari o’rtasidagi "bog’lanish" ni modellashtiradigan har qanday
narsani ifodalashi mumkin.
2.Deykstra algoritmining paydo bo’lishi
Rotterdamdan Groningenga umuman olganda berilgan shahardan ushbu
shahargacha sayohat qilishning eng qisqa yo’li nima? Bu yigirma daqiqada
mo’ljallangan eng qisqa yo’l uchun algoritm. Bir kuni ertalab men yosh yigitlar
bilan Amsterdamda xarid qilardim va charchagan edik, biz kofe choy ichib, kofe
terastasiga o’tirdik va men buni qila olamanmi yoki yo’qmi deb o’ylagandim va
keyinchalik eng qisqa yo’l uchun algoritmni yaratdim. Men aytganimdek,
yigirma daqiqalik ixtiro bo’ldi. Darhaqiqat, u 59 yil ichida, uch yil o’tib nashr
etildi. Bu kitob hali ham o’qilishi mumkin, aslida juda yaxshi. Bu juda yaxshi
bo’lgan sabablardan biri men uni qalam va qog’ozsiz tasvirladim. Keyinchalik
bilib oldimki, qalam va qog’ozsiz loyihalashtirishning afzalliklaridan biri deyarli
barcha oldini olish mumkin bo’lgan murakkabliklardan qochishingiz kerak ekan.
Oxir-oqibat, bu algoritm mening shon-shuhratimning asosiy toshlaridan biri
bo’lgan.
Dijkstra 1956 yilda Amsterdamdagi Matematik markazda ARMAC nomli
yangi kompyuterning imkoniyatlarini namoyish etish uchun dasturchi sifatida
eng qisqa yo’l muammosini o’ylab topdi. Uning maqsadi ham hisoblanmaydigan
odamlar tushunishi mumkin bo’lgan muammoni va echimni (kompyuter
tomonidan ishlab chiqariladigan) tanlash edi. U eng qisqa yo’l algoritmini ishlab
chiqdi va undan keyin uni Gollandiyada 64 ta shaharning biroz soddalashtirilgan
transport xaritasi uchun ARMAC uchun amalga oshirdi (64,ya’ni 6 bit shahar](/data/documents/b731630c-7286-47f1-bfc3-5300c55023a9/page_4.png)
![raqamini kodlash uchun etarli bo’ladi). Bir yil o’tgach, u institutning navbatdagi
kompyuterida ishlaydigan apparat-muhandislardan boshqa muammolarga duch
keldi: mashinaning orqa panelidagi pimlarni ulash uchun zarur bo’lgan simni
kamaytirish. Yechim sifatida u Primning eng kichik spanning daraxt algoritmi
deb nomlanadigan algoritmni (avvalroq Jarnikka ma’lum va shuningdek, Primni
qayta kashf qilgan) kashf etdi. Dijkstra 1959 yilda, Primdan ikki yil keyin va
Jarnikdan 29 yil o’tgach algoritmi nashr etdi.
Gollandiyalik olim Edsger Deykstra algoritmi grafning boshlang’ich
berilgan tugunidan boshlab qolgan barcha tugunlargacha bo’lgan barcha eng
qisqa yo’llarni topadi. Uning yordamida, agar barcha zarur ma’lumotlar berilgan
bo’lsa, masalan, neft va shu kabi mahsulotlarni eksport qilish uchun bitta
shahardan boshqa shaharlarning har biriga borish uchun qaysi yo’llar ketma-
ketligini tanlash afzalroq ekanligini bilib olish mumkin. Ushbu usulning salbiy
tomoni shundaki, manfiy vaznga ega bo’lgan qirralari mavjud bo’lgan graflarni
qayta ishlash imkonining mavjud emasligi, ya’ni, masalan, ba’zi tizim birorta
kompaniya uchun foydasiz bo’lgan marshrutlarni taqdim qilsa, u holda u bilan
ishlash uchun Dijkstraning algoritmidan foydalanib bo’lmaydi.
Algoritmni dasturiy ta’minotini amalga oshirish uchun ikkita massiv
kerak bo’ladi: mantiqiy toifadagi visited - tashrif buyurilgan tugunlar haqidagi
ma’lumotlarni saqlash uchun va topilgan eng qisqa yo’llar kiritiladigan butun
toifadagi - distance. G= {V, E} graf berilgan bo’lsin. V to’plamga tegishli
barcha tugunlar dastlab tashrif buyurilmagan deb belgilanadi, ya’ni visited
massivining elementlariga false qiymat berib chiqiladi. Eng afzal yo’lni topish
masalasi qaralyapti. Distance massivining har bir elementiga shunday qiymat
beriladiki, ixtiyoriy potensial yo’ldan katta bo’lsin (odatda, bu qiymatni cheksiz
katta qiymat deb qaraladi, ammo dasturda berilgan toifaning qiymatlar
diapazonidagi eng katta qiymat sifatida olinadi). Boshlang’ich nuqta sifatida s
tugun tanlanadi va unga nol yo’l belgilanadi: distance [s] = 0, chunki s-dan s-
gacha hech qanday qirra yo’q (bu usulda ilmoqlar qaralmaydi).](/data/documents/b731630c-7286-47f1-bfc3-5300c55023a9/page_5.png)
![Shundan keyin, barcha qo’shni tugunlar topiladi (s dan chiquvchi qirralar
orqali) [ularni t va u deb belgilaylik] va ular birma-bir tekshirib ko’riladi, ya’ni s
tugundan har bir tugungacha birma-bir marshrut bahosi hisoblanadi:
- distance[t]=distance[s]+ s va t orasidagi qirraning vazni;
- Distance[u]=distance[s]+ s va u orasidagi qirraning vazni.
C++ tilidagi Dijkstra algoritmining psevdokodi.
function dijkstra(G, S)
for each vertex V in G
dist[V] <- infinite
prev[V] <- NULL
If V != S, add V to Priority Queue Q
dist[S] <- 0
while Q IS NOT EMPTY
U <- Extract MIN from Q
for each unvisited neighbour V of U
temperoryDist <- dist[U] + edgeWeight(U, V)
if temperoryDist < dist[V]
dist[V] <- temperoryDist
prev[V] <- U
return dist[], prev[]
Ehtimoldan xoli emaski, u yoki bu tugunga s dan bir qancha yo’llar
bo’lishi mumkin. Shu sababli, distance massivida bu tugunga bo’lgan yo’lning
vaznini qayta ko’rib chiqish kerak bo’ladi. Shunda kattaroq (nooptimal) qiymat
yo’qotiladi va tugunga mos yo’lning vazniga kichikroq qiymat beriladi. s tugun
bilan qo’shni bo’lgan va qarab chiqilgan tugunlar tashrif buyurilgan sifatida
belgilab chiqiladi, yani visited[s]=true va natijada, s dan chiquvchi, minimal
vaznga ega bo’lgan yo’l eltuvchi tugun faol element sifatida belgilab olinadi.
Faraz qilamiz, s dan u gacha masofa t ga qaraganda qisqa bo’lsin. Kelib
chiqadiki, u tugun faollashadi va yuqoridagi kabi uning qo’shnilari (s dan
tashqari) o’rganilib chiqiladi. u tugun tashrif buyurilgan deb belgilanadi:
visited[u]=true, endi t tugun faollashadi va yuqoridagi prosedura uning uchun
takrorlanadi. Deykstra algoritmi s tugundan borish mumkin bo’lgan barcha
tugunlar tadqiq qilinmaguncha davom ettiriladi.](/data/documents/b731630c-7286-47f1-bfc3-5300c55023a9/page_6.png)
![3.Deykstra Al goritmi
Dijkstra algoritmi eng qisqa yo’l algoritmi sifatida ham tanilgan. Bu grafning
tugunlari orasidagi eng qisqa yo’lni topish uchun ishlatiladigan
algoritm. Algoritm grafning barcha boshqa nuqtalaridan boshlang’ich manba
cho’qqisidan eng qisqa yo’llar daraxtini yaratadi. U minimal kenglikdagi
daraxtdan farq qiladi, chunki ikkita cho’qqi orasidagi eng qisqa masofa grafning
barcha cho’qqilariga kiritilmasligi mumkin. Algoritm manbadan minimal
masofaga ega bo’lgan tugunlar to’plamini qurish orqali ishlaydi. Bu erda
Dijkstra algoritmi muammoni hal qilish va eng yaxshi echimni topish uchun
greedy yondashuvdan foydalanadi .
Grafdagi eng qisqa marshrutlar uchun ko’plab qidiruv algoritmlari bo’yicha,
Habreda faqatgina Floyd-Worschall algoritmining ta’rifi topildi. Ushbu algoritm
grafaning barcha vertikalari va ularning uzunligi o’rtasidagi eng qisqa yo’llarni
topadi. Ushbu maqolada Dijkstra algoritmining ishlash printsipini tasvirlab
beraman. Bu algoritm optimal yo’nalishlarni va ularning uzunligini ma’lum bir
vertikal (manba) va grafning boshqa vertikalari orasida topadi.
Dijkstra algoritmi faqat ijobiy og’irliklarga ega bo’lgan graf bilan
ishlaydi. Algoritmni bajarayotganda, tugunlar orasidagi eng qisqa yo’lni topish
uchun qirralarning og’irliklarini qo’shish kerak. Agar grafda salbiy og’irlik
bo’lsa, algoritm ishlamay qoladi. Esda tutingki, tugunni "tashrif buyurilgan" deb
belgilaganingizdan so’ng, tugunga boradigan joriy yo’l ushbu tugunga erishish
uchun eng qisqa yo’ldir. Shuning uchun, agar sizda salbiy og’irliklar bo’lsa,
umumiy og’irlik kamaytirilsa, bu bosqichni o’zgartirishi mumkin.
Bundan tashqari, Dijkstra algoritmini tushunishda savol tug’iladi:
bu BFSmi yoki DFSmi ? Xo’sh, u ham emas. Dijkstra algoritmi ustuvor birinchi
algoritmdir. Biroq, BFS va DFS algoritmlari o’rtasida ustuvorlik DFS emas,
balki BFS uchun ko’proq bo’ladi. Asosan, siz Dijkstra algoritmida BFS ning
ba’zi muhim tuzilmalarini topishingiz mumkin, ammo rostini aytganda, bu BFS
algoritmidan ancha ko’p.](/data/documents/b731630c-7286-47f1-bfc3-5300c55023a9/page_7.png)
![Deykstra algoritmini quydagi grafda ko’rib chiqsak.
Algoritm bosqichma-bosqich ishlaydi - har bir bosqichda u bitta cho’qqiga
"tashrif buyuradi" va teglarni qisqartirishga harakat qiladi. Algoritm barcha
cho’qqilarga tashrif buyurilgandan so’ng tugaydi.
Initializatsiya . A cho’qqi yorlig’ining o’zi 0 deb qabul qilinadi, boshqa
cho’qqilarning teglari cheksizlikka o’rnatiladi. Bu a dan boshqa cho’qqilargacha
bo’lgan masofalar hali ma’lum emasligini ko’rsatadi. Grafning barcha uchlari
ko’rilmagan deb belgilangan.
Algoritm bosqichi . Agar barcha cho’qqilarga tashrif buyurilgan bo’lsa, algoritm
tugaydi. Aks holda, hali tashrif buyurmagan cho’qqilardan minimal yorlig’i
bo’lgan u tepasi tanlanadi. Biz u oxirgi nuqta bo’lgan barcha mumkin bo’lgan
marshrutlarni ko’rib chiqamiz. U dan chekkalari olib boradigan cho’qqilar bu
cho’qqining qo’shnilari deyiladi. U ning har bir qo’shnisi uchun, tashrif
buyurilgan deb belgilanganlardan tashqari, joriy u yorlig’i qiymatlari
va u ni ushbu qo’shni bilan bog’laydigan chekka uzunligi yig’indisiga teng
bo’lgan yangi yo’l uzunligini ko’rib chiqing. Qabul qilingan uzunlik qiymati
qo’shnining yorlig’i qiymatidan kam bo’lsa, yorliq qiymatini qabul qilingan
uzunlik qiymati bilan almashtiring. Barcha qo’shnilarni hisobga olib, biz
tepalikni belgilaymiz u tashrif buyurgandek va algoritm qadamini takrorlang.
Misol
Rasmda ko’rsatilgan graf misolida algoritmning bajarilishini ko’rib chiqing.](/data/documents/b731630c-7286-47f1-bfc3-5300c55023a9/page_8.png)
![1-cho’qqidan qolgan barcha nuqtalargacha bo’lgan eng qisqa masofalarni topish
talab qilinsin.
Doiralar cho’qqilarni, chiziqlar ular orasidagi yo’llarni (grafning qirralarini)
ko’rsatadi. Doiralar cho’qqilarning raqamlarini ko’rsatadi, qirralarning tepasida
ularning "narxi" - yo’lning uzunligi ko’rsatilgan. Har bir cho’qqi yonida qizil
yorliq belgilanadi - bu cho’qqiga 1-cho’qqigacha bo’lgan eng qisqa yo’lning
uzunligi.
Birinchi qadam . Bizning misolimiz uchun Dijkstra algoritmidagi qadamni
ko’rib chiqing. 1-vertex minimal yorlig’iga ega.2, 3 va 6 cho’qqilari uning
qo’shnilaridir.](/data/documents/b731630c-7286-47f1-bfc3-5300c55023a9/page_9.png)
![1- cho ’ qqining birinchi qo ’ shnisi o ’ z navbatida 2- cho ’ qqidir , chunki unga
boradigan yo ’ lning uzunligi minimaldir . 1-cho’qqi orqali unga boradigan yo’l
uzunligi 1-cho’qqi yorlig’i qiymati va 1-dan 2-gacha bo’lgan chekka uzunligi
yig’indisiga teng, ya’ni 0 + 7 = 7. 2-cho’qqining joriy yorlig’i, cheksizlik,
shuning uchun 2-cho’qqining yangi yorlig’i 7 ga teng.
Biz shunga o’xshash operatsiyani 1-vertexning boshqa ikkita qo’shnisi - 3 va 6-
chi bilan bajaramiz.](/data/documents/b731630c-7286-47f1-bfc3-5300c55023a9/page_10.png)
![1-tugunning barcha qo’shnilari tekshiriladi. 1-cho’qqigacha bo’lgan joriy
minimal masofa yakuniy hisoblanadi va qayta ko’rib chiqilmaydi (bu haqiqatan
ham shunday ekanligi birinchi marta E. Dijkstra tomonidan isbotlangan ). Ushbu
tepaga tashrif buyurilganligini belgilash uchun uni grafdan kesib o’ting.
Ikkinchi qadam . Algoritm bosqichi takrorlanadi. Yana biz ko’rilmagan
cho’qqilarning "eng yaqinini" topamiz. Bu 7 deb belgilangan 2-cho’qqi.
Yana biz tanlangan cho’qqining qo’shnilarining teglarini kamaytirishga harakat
qilamiz, ular orqali 2-cho’qqi orqali o’tishga harakat qilamiz. Vertex 2 ning
qo’shnilari 1, 3 va 4 uchlaridir.
2 cho’qqisining birinchi (tartibda) qo’shnisi 1 cho’qqidir. Lekin u allaqachon
tashrif buyurilgan, shuning uchun biz 1-cho’qqi bilan hech narsa qilmaymiz.
2-cho’qqining keyingi qo’shnisi 3-vertexdir, chunki u kirmagan deb belgilangan
cho’qqilarning minimal yorlig’iga ega. Agar siz unga 2 dan o’tsangiz, unda
bunday yo’lning uzunligi 17 ga teng bo’ladi (7 + 10 = 17). Ammo uchinchi](/data/documents/b731630c-7286-47f1-bfc3-5300c55023a9/page_11.png)
![cho’qqining joriy yorlig’i 9 ni tashkil etadi, bu 17 dan kichik, shuning uchun
yorliq o’zgarmaydi.
2-cho’qqining yana bir qo’shnisi 4-cho’qqidir. Agar siz unga 2-chi orqali
o’tsangiz, unda bunday yo’lning uzunligi 2-cho’qqigacha bo’lgan eng qisqa
masofa va 2 va 4 cho’qqilar orasidagi masofa yig’indisiga teng bo’ladi, ya’ni ,
22 (7 + 15 = 22) . 22<<math>\infty</math> bo’lgani uchun 4-cho’qqining
yorlig’ini 22 ga o’rnatdik.
2-vertexning barcha qo’shnilari ko’rib chiqildi, biz unga bo’lgan masofani
muzlatib qo’yamiz va tashrif buyurilgan deb belgilaymiz.](/data/documents/b731630c-7286-47f1-bfc3-5300c55023a9/page_12.png)
![Uchinchi qadam . Algoritmning qadamini 3-cho’qqini tanlab takrorlaymiz. Uni
“qayta ishlash”dan so’ng biz quyidagi natijalarni olamiz:
Keyingi qadamlar . Qolgan cho’qqilar uchun algoritmning qadamini
takrorlaymiz. Bular mos ravishda 6, 4 va 5 uchlari bo’ladi.](/data/documents/b731630c-7286-47f1-bfc3-5300c55023a9/page_13.png)
![Algoritmning bajarilishini yakunlash . Algoritm boshqa cho’qqilarni qayta
ishlash mumkin bo’lmaganda tugaydi. Bu misolda barcha cho’qqilar chizilgan,
lekin har qanday misolda shunday bo’ladi deb o’ylash xatodir - agar ularga etib
bo’lmasa, ya’ni graf uzilgan bo’lsa, ba’zi cho’qqilar chizilmagan holda qolishi
mumkin. Algoritmning natijasi oxirgi rasmda ko’rinadi: 1 cho’qqidan 2 gacha
bo’lgan eng qisqa yo’l 7, 3 gacha - 9, 4 - 20, 5 - 20, 6 – 11 bo ’ lishini ko ’ rishimiz
mumkin .
Grafdagi ma ’ lum bir manba tuguniga ega bo ’ lgan algoritm bu tugun bilan har
bir boshqa o ’ rtasidagi eng qisqa yo ’ lni topadi . Bundan tashqari , bitta tugunning
eng qisqa yo ’ llarini to ’ xtatish yo ’ li bilan bitta maqsadli tugunga maqsad
tuguniga eng qisqa yo ’ l aniqlanganidan keyin algoritm aniqlandi . Masalan , agar](/data/documents/b731630c-7286-47f1-bfc3-5300c55023a9/page_14.png)
![graf tugunlari shaharlarni ifodalasa va chekka xarajatlari to ’ g ’ ridan - to ’ g ’ ri yo ’ l
bilan bog ’ langan shaharlarning juftliklari o ’ rtasidagi masofani ifodalaydi
( oddiylik uchun , qizil chiroqlar , ishlamaydigan belgilar , pullik yo ’ llar va boshqa
to ’ siqlarni e ’ tiborsiz qoldirish uchun ), Dijkstra algoritmi ishlatilishi mumkin Bir
shahar va boshqa shaharlarning eng qisqa yo ’ lini topish . Qisqa yo ’ l
algoritmining keng tarqalgan qo ’ llanilishi tarmoqni boshqarish protokollaridir ,
Shuningdek , Jonson kabi boshqa algoritmlarda ham subroutin sifatida
qo ’ llaniladi .
Dijkstra algoritmida musbat tamsay yoki haqiqiy sonlar bo’lgan etiketlar
ishlatiladi, bu aniq zaif tartibga solingan. Qiziqarli tomoni shundaki, Dijkstra
aniq belgilangan qisman tartibga ega bo’lgan va keyingi teglar (bir chekkadan
o’tib ketganda keyingi yorliq) monotonik ravishda kamaymaslik sharti bilan
aniqlangan teglardan foydalanish uchun umumlashtirilishi mumkin. Ushbu
umumlashma umumiy Dijkstra qisqa yo’l algoritmi deb ataladi.
Bu asimptotik jihatdan cheklanmagan bo’lmagan graflar uchun eng tez-
tez ma’lum bo’lgan yagona manbali eng qisqa yo’l algoritmidir. Salbiy
og’irliklar shu bilan birga, ixtisoslashgan variantlar (masalan, cheklangan to’liq
sonlar, yo’naltirilgan asiklik grafalar va h.k.) ixtisoslashgan variantlarda batafsil
ravishda takomillashtirilishi mumkin. Ba’zi sohalarda, xususan sun’iy aql,
Dijkstra algoritmi yoki uning bir nusxasi bir xil xarajat qidiruvi deb nomlanadi
va eng yaxshi qidiruvga oid umumiy g’oyaning misoli sifatida
shakllanadi. Algoritm Dijkstra algoritmining robot harakati rejalashtirishda
boshlang’ich tugunidan (pastki chap, qizil) maqsad tuguniga (yuqori o’ng,
yashil) yo’l topish. Ochiq tugunlar "noaniq" to’plamni aks ettiradi ("novisited"
tugunlar to’plami). To’ldirilgan tugunlar tashrif buyuriladi, rangi masofani
ifodalaydi: yashil, qanchalik yaqin. Dijkstra algoritmida 0 ga teng bo’lgan
heuristik usulni qo’llaganidek, barcha yo’nalishdagi tugunlar bir xil tarzda
o’rganilib, dyuym to’lqinlari ko’rinishida ko’proq yoki kamroq ko’rinadi.Biz
boshlayotgan tugunni boshlang’ich tugun deb ataymiz. Y tugunining masofa
boshlang’ich tugunidan Y gacha bo’lgan masofa bo’lsin. Dijkstra algoritmi ba’zi](/data/documents/b731630c-7286-47f1-bfc3-5300c55023a9/page_15.png)
![boshlang’ich masofani qadrlaydi va ularni bosqichma-bosqich
takomillashtirishga harakatqiladi.Barcha tugunlarni kutmasdan belgilang.
Ko’rinmas to’siq deb nomlangan barcha ko’rinmaydigan tugunlarni yaratish.Har
bir tugunga vaqtinchalik masofa qiymatini belgilang: bizning boshlang’ich
tugunimiz uchun nolga va boshqa barcha tugunlar uchun cheksiz qiymatga
sozlang. Boshlang’ich tugunni nol deb belgilang.Joriy tugun uchun, hozirgi
tugunlar orqali barcha ko’rinmagan qo’shnilarini hisobga oling va o’z vaqt
oralig’ini hisoblang. Yangi tayinlangan vaqtinchalik masofani joriy tayinlangan
qiymat bilan taqqoslang va undan kichikroqni tayinlang. Masalan, agar A
tugmasi 6 ga teng bo’lsa va qo’shni B bilan bog’laydigan chetning uzunligi 2
bo’lsa, B dan A gacha masofa 6 + 2 = 8 bo’ladi. Agar B ilgari belgilangan
bo’lsa, 8 dan katta masofa, keyin uni 8 ga o’zgartiring. Aks holda, joriy
qiymatni saqlang.Biz tugunning barcha ko’rinmagan qo’shnilarini hisobga olgan
holda tugallangandan so’ng, joriy tugunni tashrif buyurgan deb belgilab qo’ying
va uni ko’rinmas to’siqdan olib tashlang. Tashlangan tugma hech qachon
tekshirilmaydi.Agar maqsad tugunni tashrif buyurilgan deb belgilansa (ikki
maxsus tugma o’rtasida marshrutni rejalashtirganda) yoki ko’rinmagan
guruhdagi tugunlar orasida eng kichik masofa cheksiz bo’lsa (to’liq traversalni
rejalashtirayotganda, boshlang’ich tugun bilan va bekor qilinmagan tugunlarni)
keyin to’xtating. Algoritm tugadi.
Aks holda, eng kichik vaqt oralig’i bilan belgilanmagan ko’rinmaydigan tugunni
tanlang, uni yangi «joriy tugun» deb o’rnating va 3-bosqichga qayting.
Marshrutni rejalashtirishda, aslida maqsadli tugun yuqorida ko’rsatilgan
"kutilgan" bo’lguncha kutishning hojati yo’q: maqsadli tugun barcha
"kutilmagan" tugunlar orasidagi eng kichik masofani egallab olgandan so’ng
to’xtashi mumkin
Izoh: tushunish qulayligi uchun bu munozarada choralar, yo’llar va xarita
atamalaridan foydalaniladi, ammo rasmiy terminologiyada bu atamalar navbati
bilan vertex, kenar va graf hisoblanadi.](/data/documents/b731630c-7286-47f1-bfc3-5300c55023a9/page_16.png)
![Bir shahar xaritasida ikkita shahar o’rtasida eng qisqa yo’lni
topmoqchiman: boshlang’ich nuqtasi va borar joyi. Dijkstra algoritmi dastlab
masofani masofani (boshlang’ich nuqtadan) xaritada har bir kesib o’tish joyiga
cheksizlik bilan belgilaydi. Bu cheksiz masofa mavjudligini anglatmaslik uchun
emas, balki bu chorrahalar hali kelmaganligini ta’kidlash uchun qilingan. Ushbu
usulning ayrim variantlari kesishmalarning masofalaridan ajralmagan holda
qoldiriladi. Endi har bir iteratsiyada joriy kesishni tanlang. Birinchi iteratsiya
uchun joriy kesish boshlanish nuqtasi bo’ladi va unga masofa (kesishma
yorlig’i) nol bo’ladi. Keyingi izlanishlar uchun (keyingi birinchi), joriy kesishish
boshlang’ich nuqtaga eng yaqin ko’rinmaydigan kesishish bo’ladi (bu oson
topiladi).Joriy kesishuvdan to’g’ridan-to’g’ri bog’langan har qanday
ko’rinishdagi kesishma masofani yangilang. Buning sababi, mavjud bo’lmagan
kesishma va joriy kesishma qiymatlari o’rtasidagi masofaning umumiy
miqdorini belgilash va keyinchalik kiritilmagan kesishishning ushbu qiymatga
(summaga) kiritilmasligi, agar u kutilmagan kesishma oqimining qiymatidan
kamroq bo’lsa. Haqiqatdan ham, agar kesishma yo’li orqali unga yo’l oldindan
ma’lum bo’lgan yo’llardan qisqartirilsa, kesishma qayta belgilanadi. Eng qisqa
yo’lni identifikatsiyalashni engillashtirish uchun, qalamda yo’lni ko’rsatgich
bilan belgilab qo’ying va uni ko’rsatgan barcha belgilarni o’chirib tashlang. Har
bir qo’shni kesib o’tish joyiga masofani yangilaganingizdan so’ng, joriy
kesishuvni tashrif buyurilgan deb belgilang va eng kichik masofani
(boshlang’ich nuqtadan) yoki eng pastki belgini - mavjud kesishma sifatida
tanlamang. Ko’rilgan deb nomlangan uchastka boshlang’ich nuqtadan eng qisqa
yo’l bilan etiketlanadi va qayta ko’rib chiqilmaydi yoki qaytarilmaydi.
Qo’shni uchastkalarni eng qisqa masofalar bilan yangilab borish, mavjud
kesishishni tashrif buyurgan deb belgilash va maqsadni tashrif buyurgan deb
belgilaguningizcha eng yaqin ko’rinmaydigan kesma tomonga o’tish jarayonini
davom ettiring. Belgilangan joyni tashrif buyurganingiz kabi belgilab
qo’yganingizdan so’ng (siz tashrif buyurgan har qanday kesishmada bo’lgani
kabi), siz boshlash nuqtasidan eng qisqa yo’lni belgilab oldingiz va orqadagi](/data/documents/b731630c-7286-47f1-bfc3-5300c55023a9/page_17.png)
![o’qlar orqasidan yo’lni orqaga qaytarasiz. Algoritmni amalga oshirishda, bu
odatda tugma tugunlaridan boshlang’ich tuguniga qadar tugunlarni ota-onalariga
rioya qilish yo’li bilan amalga oshiriladi (algoritm maqsadli tugunga yetgandan
keyin); Shuning uchun biz har bir tugunning ota-onasini kuzatib boramiz.Ushbu
algoritm kutilayotgan maqsadga yo’naltirilgan to’g’ridan-to’g’ri "qidiruv"
harakatlariga yo’l qo’ymaydi. Aksincha, kelgusi "joriy" kesishishni aniqlashda
yagona e’tibor uning boshlang’ich nuqtasigacha bo’lgan masofasidir. Shuning
uchun ushbu algoritm boshlang’ich nuqtadan tashqariga chiqadi, interaktiv
ravishda maqsadga etgunga qadar eng qisqa yo’l masofasi jihatidan yaqinroq
bo’lgan har bir tugunni hisobga oladi. Shu tarzda tushunilsa, algoritm qanday
qilib eng qisqa yo’lni topish kerakligi aniq.
4. Eng qisqa yo’llar masalalarining turlari
Yo’l tarmoqlari atlasi (karta) qismi berilgan bo’lib, undan A va B nuqtalar
orasidagi “eng yahshi” marshrutni topish kerak bo’lsin. “Eng yahshi” marshrutni
ko’p faktorlar belgilashi mumkin, masalan, tezlik cheklangan holda marshrutni
o’tish vaqti, o’tish kerak bo’lgan shaharlar soni va boshqalar.
Biz masalani eng qisqa yo’llar faktori bo’yicha yechamiz. Masalaning
modeli turlar yordamida tuziladi. Uzluksiz G turni har bir qirrasiga uning
uzunligiga teng qiymat berilgan ko’rinishida tuzamiz. Bunday turda masofa
qirralar yig’indisiga teng bo’ladi. Masalaning maqsadi ikkita berilgan uchlar
orasidagi eng qisqa marshrutni topishdir.
Umuman, eng qisqa yo’llar masalalari kombinator optimallashtirishning
fundamental muammolaridandir. Ularning bir necha turlari mavjud, masalan,
ikkita berilgan uchlar orasida, berilgan va qolgan barcha uchlar orasida ,shu kabi
turdagi har bir uchlar juftliklari orasida va boshqalar.
5.Deykstra algoritmning so’zli tavsifi
Dijkstra algoritmi eng qisqa yo’l algoritmi sifatida ham tanilgan. Bu
grafning tugunlari orasidagi eng qisqa yo’lni topish uchun ishlatiladigan
algoritm. Algoritm grafning barcha boshqa nuqtalaridan boshlang’ich manba](/data/documents/b731630c-7286-47f1-bfc3-5300c55023a9/page_18.png)
![cho’qqisidan eng qisqa yo’llar daraxtini yaratadi. U minimal kenglikdagi
daraxtdan farq qiladi, chunki ikkita cho’qqi orasidagi eng qisqa masofa grafning
barcha cho’qqilariga kiritilmasligi mumkin. Algoritm manbadan minimal
masofaga ega bo’lgan tugunlar to’plamini qurish orqali ishlaydi. Bu erda
Dijkstra algoritmi muammoni hal qilish va eng yaxshi echimni topish uchun
ochko’z yondashuvdan foydalanadi.
Dijkstra algoritmi sahna ortida qanday ishlashini bilish uchun uni batafsil
tushunish uchun quyidagi bosqichlarni ko’rib chiqaylik:
1. Avvalo, biz barcha cho’qqilarni ko’rilmagan cho’qqi sifatida belgilaymiz
2. Keyin, biz manba cho’qqisini 0, boshqa barcha cho’qqilarni cheksizlik
sifatida belgilaymiz
3. Manba cho’qqisini joriy cho’qqi sifatida ko’rib chiqing
4. Joriy cho’qqidagi chetning og’irligini qo’shish orqali barcha qo’shni
cho’qqilarning yo’l uzunligini joriy cho’qqidan hisoblang.
5. Endi, agar yangi yo’l uzunligi oldingi yo’l uzunligidan kichikroq bo’lsa,
uni almashtiring, aks holda uni e’tiborsiz qoldiring
6. Joriy cho’qqining qo’shni cho’qqisiga tashrif buyurganingizdan keyin
tashrif buyurilgan deb belgilang
7. Yangi joriy cho’qqi sifatida yo’l uzunligi eng kichik bo’lgan cho’qqini
tanlang va 4-bosqichga qayting.
8. Barcha tepaliklar tashrif buyurilgan deb belgilanmaguncha ushbu
jarayonni takrorlang.
Algoritmdan o’tganimizdan so’ng, biz manba cho’qqisini orqaga qaytarishimiz
va eng qisqa yo’limizni topishimiz mumkin.
Misol:
Algoritmni tushunish uchun quyidagi misolni ko’rib chiqamiz. Bu erda bizga
vaznli graf berilgan va biz grafning manba cho’qqisi sifatida "A" cho’qqisini
tanlaymiz.](/data/documents/b731630c-7286-47f1-bfc3-5300c55023a9/page_19.png)
![Algoritm manba cho’qqisidan boshqa har bir cho’qqigacha bo’lgan eng qisqa
yo’lni yaratganligi sababli, biz manba cho’qqisining o’ziga bo’lgan masofasini
"0" qilib o’rnatamiz. Manba cho’qqisidan boshqa barcha cho’qqilargacha
bo’lgan masofa hali aniqlanmagan, shuning uchun biz uni cheksizlik yordamida
ifodalaymiz.
Hozircha ko’rilmagan tugunlar ro’yxati quyidagicha bo’ladi: {B, C, D, E}
Bu erda biz "A" tugunidan uning qo’shni cho’qqisigacha bo’lgan masofani
tekshirishni boshlaymiz. Siz qo’shni cho’qqilarni mos ravishda "10" va "3"
og’irliklari bilan "B" va "C" ko’rishingiz mumkin. Esda tutingki, ikkita tepani
darhol eng qisqa yo’lga qo’shishingiz shart emas.
Birinchidan, biz cheksizlikdan berilgan og’irliklargacha bo’lgan masofani
yangilaymiz. Keyin yangilangan og’irliklarga qarab manba tuguniga eng yaqin
tugunni tanlashimiz kerak. Uni tashrif buyurilgan deb belgilang va uni yo’lga
qo’shing.](/data/documents/b731630c-7286-47f1-bfc3-5300c55023a9/page_20.png)
![Quyida ko’rsatilganidek, biz B cho’qqisini cheksizlikdan 10 ga va C cho’qqisini
cheksizlikdan 3 ga yangilaymiz.
Endi tashrif buyurilgan cho’qqi sifatida kichikroq yo’l uzunligi bilan cho’qqini
tanlang va uni javobga qo’ying. Shuning uchun, ko’rilmagan tugunlar ro’yxati
{B, D, E}](/data/documents/b731630c-7286-47f1-bfc3-5300c55023a9/page_21.png)
![Endi biz eng qisqa yo’lni topish uchun yangi qo’shni cho’qqini tahlil qilishimiz
kerak. Shunday qilib, biz tashrif buyurilgan cho’qqining qo’shni tugunlariga
tashrif buyuramiz va kerak bo’lganda yo’l uzunligini yangilaymiz. Bu erda
bizda B, D va E nuqtalari ‘A’ tugunlari va ‘C’ tugunlariga ulashgan cho’qqi
sifatida mavjud. Shuning uchun, biz quyidagi rasmda ko’rsatilganidek, barcha
uchta cho’qqining yo’lini cheksizlikdan tegishli og’irliklarigacha yangilaymiz.
E’tibor bering, "B" tugun "A" tuguniga to’g’ridan-to’g’ri ulangan, shuning
uchun "B" tugunining og’irligi ko’rsatilgandek bo’ladi. Ammo ‘D’ tugunlari va
‘E’ tugunlari uchun yo’l ‘C’ tugunlari orqali hisoblanadi va shuning uchun bu
tepaning og’irligi 11 va 5 ga teng bo’ladi, chunki biz A->C-> yo’lidan
qirralarning og’irligini qo’shamiz. D va A->C->E.](/data/documents/b731630c-7286-47f1-bfc3-5300c55023a9/page_22.png)
![Endi yuqoridagi jadvaldan eng qisqa yo’lni tanlash manba cho’qqisidan eng
qisqa masofa 5 ga teng bo’lgan "E" tugunini tanlashga olib keladi. Va shuning
uchun tashrif buyurilmagan tugunlar ro’yxati {B, D}](/data/documents/b731630c-7286-47f1-bfc3-5300c55023a9/page_23.png)
![Barcha cho’qqilarga tashrif buyurilgunga qadar jarayonni takrorlang. Bu erda
"B" cho’qqisi va "D" cho’qqisi ikkalasi ham qo’shni cho’qqi hisoblanadi va
ikkala cho’qqining manba tugunidan eng qisqa masofasi quyidagi rasmda
ko’rsatilganidek o’zgarmaydi.](/data/documents/b731630c-7286-47f1-bfc3-5300c55023a9/page_24.png)
![Shuning uchun, "B" cho’qqisining og’irligi "D" cho’qqisiga nisbatan
minimaldir, shuning uchun biz uni tashrif buyurilgan tugun sifatida belgilaymiz
va uni yo’lga qo’shamiz. Kirilmagan tugunlar ro yxati {D} bo ladiʻ ʻ](/data/documents/b731630c-7286-47f1-bfc3-5300c55023a9/page_25.png)
!["B" cho’qqisiga tashrif buyurganimizdan so’ng, "D" cho’qqisiga tashrif
buyurishimiz qoladi. Ehtiyotkorlik bilan e’tibor bergan bo’lsangiz, manba
cho’qqisidan "D" cho’qqigacha bo’lgan masofa avvalgisidan o’zgartirilishi
mumkin, ya’ni "D" cho’qqisiga to’g’ridan-to’g’ri "C" cho’qqi orqali tashrif
buyurish o’rniga, biz "B" cho’qqisiga tashrif buyurishimiz mumkin. umumiy
masofa 9. Buning sababi, biz quyida ko’rsatilgandek A->C->B->D (3+4+2=9)
kabi qirralarning og’irligini qo’shamiz.
Shunday qilib, algoritmning yakuniy natijasi {A, C, E, B, D} bo’ladi.](/data/documents/b731630c-7286-47f1-bfc3-5300c55023a9/page_26.png)
![6. Deykstra algoritmning C++ da kodi
C++ tilidagi Dijkstra algoritmining psevdokodi
1. function dijkstra(G, S)
2. for each vertex V in G
3. dist[V] <- infinite
4. prev[V] <- NULL
5. If V != S, add V to Priority Queue Q
6. dist[S] <- 0
7. while Q IS NOT EMPTY
8. U <- Extract MIN from Q
9. for each unvisited neighbour V of U
10. temperoryDist <- dist[U] + edgeWeight(U, V)
11. if temperoryDist < dist[V]
12. dist[V] <- temperoryDist](/data/documents/b731630c-7286-47f1-bfc3-5300c55023a9/page_27.png)
![13. prev[V] <- U
14. return dist[], prev[]
Quyidagi algoritmda kodi u ning vertex’si min dist [u] ga teng, u vertex
majmuasida eng kam dist [u] qiymati bo’lgan vertex u ni izlaydi. uzunligi (u, v)
ikki qo’shni n-tugunni u va v o’rtasidagi chegara uzunligini qaytaradi. 18-satrda
o’zgaruvchining pastki qismi - ildiz tugunidan qo’shni tugunga yo’lning
uzunligi v U orqali o’tish kerak edi. Ushbu yo’l v uchun saqlangan joriy qisqa
yo’ldan qisqartirsa, u joriy yo’l bu pastki yo’l bilan o’zgartiriladi. Avvalgi qator
manbaga eng qisqa yo’lni olish uchun manba grafasida "keyingi-hop" tuguniga
ko’rsatgich bilan to’ldiriladi.
Agar vertices manbai va maqsad o’rtasida eng qisqa yo’l bilan qiziqsak, agar u
maqsad bo’lsa, 15-sathdan keyin qidiruvni tugatishimiz mumkin. Keling, biz
qaytadan ierarxiya orqali manbaga eng qisqa yo’lni o’qiy olishimiz mumkin:
1.//boshlash.
3.//Faqat vertexga o’tish mumkin bo’lsa, biror narsani bajaring.
4.//S-to’plam bilan eng qisqa yo’lni tanlang.
5.//Tepalikka suyakka suring.
6.// maqsaddan manbaga aylantirish.
8//V manbadan tortib v. Ga noma’lum masofa.
9//Predessori v.
12//Asosiy ko’chadan.
13//Eng yaxshi vertexni olib tashlang.
14//faqat v ning hali ham Q.
Boshlash davridagi barcha tugunlar bilan ustuvor navbatni to’ldirishning
o’rniga, uni faqat manbai bo’lishi uchun ishga tushirish mumkin; unda, agar
pastki <dist [v] blok ichida bo’lsa, tugma, navbatda bo’lmasa (pastroqqa
operatsiyani bajarish o’rniga) kiritilishi kerak. [erishish uchun ishlatilishi
mumkin.
С++ dasturlash tilida quyidagicha bo’ladi:](/data/documents/b731630c-7286-47f1-bfc3-5300c55023a9/page_28.png)
![1-ko’rinish
#include<iostream>
#include<climits>
using namespace std;
int miniDist( int distance[], bool Tset[]) // minimal masofani topish
{
int minimum = INT_MAX,ind;
for ( int k = 0 ;k < 6 ;k ++ )
{
if (Tset[k] == false && distance[k] <= minimum)
{
minimum = distance[k];
ind = k;
}
}
return ind;
}
void DijkstraAlgo( int graph[ 6 ][ 6 ], int src) // qo’shnilik matritsasi
{
int distance [ 6 ]; // har bir tugun uchun minimal masofani hisoblash uchun
massiv
bool Tset[ 6 ]; // Har bir tugun uchun tashrif buyurilgan va tashrif buyurilmagan
belgilash uchun mantiqiy massiv
for ( int k = 0 ; k < 6 ; k ++ )
{](/data/documents/b731630c-7286-47f1-bfc3-5300c55023a9/page_29.png)
![distance[k] = INT_MAX;
Tset[k] = false;
}
distance[src] = 0 ; // Manba tepasi masofasi 0 ga o’rnatiladi
for ( int k = 0 ; k < 6 ; k ++ )
{
int m = miniDist(distance,Tset);
Tset[m] = true;
for ( int k = 0 ; k < 6 ; k ++ )
{
// qo’shni vertex masofasini yangilash
If ( ! Tset [k] && graph[m][k] && distance[m] != INT_MAX &&
distance[m] + graph[m][k] < distance[k])
distance[k] = distance[m] + graph[m][k];
}
}
cout << " Vertex\t\tManba cho’qqisidan masofa " << endl;
for ( int k = 0 ; k < 6 ; k ++ )
{
char str = 65 + k;
cout << str << " \t\t\t " << distance[k] << endl;
}
}
int main()
{
int graph[ 6 ][ 6 ] = {
{ 0 , 1 , 2 , 0 , 0 , 0 },](/data/documents/b731630c-7286-47f1-bfc3-5300c55023a9/page_30.png)
![{ 1 , 0 , 0 , 5 , 1 , 0 },
{ 2 , 0 , 0 , 2 , 3 , 0 },
{ 0 , 5 , 2 , 0 , 2 , 2 },
{ 0 , 1 , 3 , 2 , 0 , 1 },
{ 0 , 0 , 0 , 2 , 1 , 0 }};
DijkstraAlgo(graph, 0 );
return 0 ;
}
Chiqish
Vertex Manbadan masofa
A 0 B 1 C 2 D 4 E 2 F 3
Vaqtning murakkabligi
Dijkstra algoritmining vaqt murakkabligi O(V^2) ga teng, bu erda V - grafdagi
cho’qqilar soni. Biroq, agar kirish grafigi qo’shnilik ro’yxati (grafni ko’rsatish
usuli) yordamida tasvirlangan bo’lsa, unda vaqt murakkabligini ikkilik to’p
yordamida O(E log V) ga kamaytirish mumkin.
Dijkstra algoritmining fazoviy murakkabligi O(V) ga teng, bu erda V - grafning
umumiy cho’qqilari soni. Buning sababi shundaki, biz ushbu barcha uchlarni
ro’yxatda chiqish sifatida saqlashimiz kerak.
2-ko’rinish:
# include <iostream>
# include <climits>
using namespace std ;](/data/documents/b731630c-7286-47f1-bfc3-5300c55023a9/page_31.png)
![int miniDist ( int distance [], bool Tset []) // finding minimum
distance
{
int minimum = INT_MAX , ind ;
for ( int k =0 ; k <6 ; k ++ )
{
if ( Tset [ k ] ==false && distance [ k ] <= minimum )
{
minimum = distance [ k ];
ind = k ;
}
}
return ind ;
}
void DijkstraAlgo ( int graph [ 6 ][ 6 ], int src ) // qo'shnilik
matritsasi
{
int distance [ 6 ]; // // har bir tugun uchun minimal masofani
hisoblash uchun massiv
bool Tset [ 6 ]; // Har bir tugun uchun tashrif buyurilgan va
tashrif buyurilmagan belgilash uchun mantiqiy massiv
for ( int k = 0 ; k <6 ; k ++ )
{
distance [ k ] = INT_MAX ;
Tset [ k ] = false ;
}
distance [ src ] = 0 ; // Manba tepasi masofasi 0 ga o' qulay
for ( int k = 0 ; k <6 ; k ++ )
{
int m = miniDist ( distance , Tset );
Tset [ m ] =true ;
for ( int k = 0 ; k <6 ; k ++ )
{
// qo'shni cho'qqilarning masofasini yangilash
if ( ! Tset [ k ] && graph [ m ][ k ] && distance [ m ] != INT_MAX &&
distance [ m ] + graph [ m ][ k ] < distance [ k ])
distance [ k ] = distance [ m ] + graph [ m ][ k ];
}
}
cout << " Vertex\t\tManba cho'qqisidan masofa " << endl ;
for ( int k = 0 ; k <6 ; k ++ )
{](/data/documents/b731630c-7286-47f1-bfc3-5300c55023a9/page_32.png)
![char str =65+ k ;
cout << str << "\t\t\t" << distance [ k ] << endl ;
}
}
int main ()
{
int graph [ 6 ][ 6 ] = {
{ 0 , 1 , 2 , 0 , 0 , 0 },
{ 1 , 0 , 0 , 5 , 1 , 0 },
{ 2 , 0 , 0 , 2 , 3 , 0 },
{ 0 , 5 , 2 , 0 , 2 , 2 },
{ 0 , 1 , 3 , 2 , 0 , 1 },
{ 0 , 0 , 0 , 2 , 1 , 0 }};
DijkstraAlgo ( graph , 0 );
return 0 ;
}
Chiqish:
7.Tegishli muammolar va algoritmlar
Dijkstra original algoritmining funktsiyalari turli modifikatsiyalar bilan
kengaytirilishi mumkin. Masalan, ba’zida matematik jihatdan maqbul
bo’lmagan echimlarni taqdim etish maqsadga muvofiqdir. Kamdan-kamroq
optimal echimlar topilgan ro’yxatini olish uchun maqbul echim avval hisoblab
chiqilgan. Optimal eritmada ko’rinadigan bitta qirrali grafadan chiqariladi va bu
yangi grafka optimal echim hisoblanadi. Dastlabki eritmaning har bir qirrasi o’z
navbatida bekor qilinadi va yangi qisqa yo’l aniqlanadi. Keyinchalik, ikkilamchi
eritmalar birinchi optimal eritmaning so’ng baholanadi va taqdim Manba tepasidagi masofa](/data/documents/b731630c-7286-47f1-bfc3-5300c55023a9/page_33.png)
![etiladi.Dijkstraning algoritmi, odatda, ulanish-davlat marshrutlash protokollari,
OSPF va IS-IS eng keng tarqalgan bo’lib turadigan ish printsipi
hisoblanadi.Dijkstra algoritmidan farqli o’laroq, Bellman-Ford algoritmi
gorizontal manba vertolyotidan salbiy tsiklga ega bo’lmasa, salbiy qirrali grafa
bilan ishlatilishi mumkin. Bunday aylanishlarning mavjudligi eng kichik yo’l
yo’qligini anglatadi, chunki har bir tsiklda aylanish jarayonida umumiy og’irlik
pastga aylanadi. Dijkstra algoritmini salbiy og’irlik chekkalarini Bellman-Ford
algoritmiga (salbiy qirralarni olib tashlash va salbiy davrlarni aniqlash)
birlashtirish yo’li bilan moslashtirish mumkin, bunday algoritm Jonsonning
algoritmi deb ataladi.
A * algoritmi Dijkstra ning algoritmini umumlashtirish, agar maqsadga
"masofadan" pastroq bo’lgan cheklovni ta’minlaydigan qo’shimcha ma’lumot
mavjud bo’lsa, o’rganilishi kerak bo’lgan subgraf o’lchamini qisqartiradi. Ushbu
yondashuv chiziqli dasturlash nuqtai nazaridan qaralishi mumkin: eng qisqa
yo’llarni hisoblash uchun tabiiy chiziqli dastur mavjud va uning ikkilamchi
chiziqli dasturiga echimlarni kiritish mumkin va ular faqat izchil sezgirlikni
shakllantirsa (taxminan, so’zma-so’z konventsiyalari farqlanadi) adabiyotda
joydan joygacha). Ushbu mumkin bo’lgan ikkilangan / izchil topilmalar salbiy
bo’lmagan past narxni belgilaydi va A * bu Dijkstra algoritmini ushbu kam
xarajatlar bilan boshqaradi. Agar ikkilamchi qabul qilishning zaif holatini
qondirsa, A * o’rniga Bellman-Ford algoritmiga ko’proq mos keladi.
Dijkstraning algoritmining asoslanishi jarayon Primet algoritmida
ishlatiladigan ochko’z jarayonga o’xshaydi. Primning maqsadi grafadagi barcha
tugunlarni bir-biriga bog’lovchi minimal spanning daraxtni topishdir; Dijkstra
faqat ikkita tugun bilan bog’liq. Primer, yo’lning umumiy og’irligini
boshlang’ich tugunidan, faqatgina individual qirralarni baholaydi. Kichkina
birinchi qidiruvni Dijkstra algoritmini taqqoslanmagan graflarda ko’rib chiqish
mumkin, bu erda navbatdagi navbat FIFO navbatiga ziyon beradi.Tez marshing](/data/documents/b731630c-7286-47f1-bfc3-5300c55023a9/page_34.png)
![usuli Dijkstra algoritmining uchburchak meshidagi geodezial masofani
hisoblaydigan uzluksiz versiyasidir.](/data/documents/b731630c-7286-47f1-bfc3-5300c55023a9/page_35.png)
![X ulosa
Xulosa qilib aytganda A lgoritm bilan ishlash barcha turdagi dasturlash
tillarida ishlash uchun kerak b o' ladi . Algoritmsiz biror bir dasturlash tilida
dastur yaratib bulmaydi . H ar bir dasturning dastlab algoritmini yaratib olish
zarur . A gar biz dasturimizning ketma - ketligini bilmasak , u dastur biz
uylagandan kuproq xajmni egallashi mumkin ekan . C ++ dasturlash tilida
malumotlarni izlash , saralash, qayta ishlash kabi amallarni yuqorida kursatib
utilganidagidek bir va ikki ulchovli massivlarda bajarilganini kurib bilim va
kunikmalarga ega bo’ldiz. C++ dasturi strukturasi xaqida, belgilar bayoni,
algoritm va dastur tushunchasi, malumotlarni kiritish va chiqarish operatorlari
xamda dasturda ishlatiladigan toifalar, ifodalar va kunikmalarini ko’rib chiqdiz .
Algoritmlash va dasturlash tillari buyicha yozilgan bir nechta kitoblar bilan
tanishib chiqdiz va ulardan kerakli malumotlarni oldiz .Bu kurs ishida Deyskra
algoritmining ishlash prinsplarini ko’rib uning ishlashini dasturlarda amaliy
ko’rib chiqdik.
Graflar elementlarni, odamlarni va ob’ektlarni bog’lash uchun ishlatiladi
va Dijkstra algoritmi grafdagi ikkita nuqta orasidagi eng qisqa masofani
aniqlashda sizga yordam beradi. Deykstra algoritmi haqiqiy dunyoda juda
muhim bo’lgani uchun uni to’g’ri o’rganish va tushunish yaxshiroqdir.](/data/documents/b731630c-7286-47f1-bfc3-5300c55023a9/page_36.png)
![Foydalangan adabiyotlar:
Adabiyotlar
В . А . Успенский , А . Л . Семенов . Теория алгоритмов: основные открытия
и
приложения. – М: Наука, 1987, 287 с.
2. Т..Кормен, Ч.Лейзерсон, Р.Ривест. Алгоритмы: построение и анализ
Сер:Классические учебники. М.: МЦНМО, 2001.- 960 с.
3. Тыугу Х. Концептуальное программирование. М: Наука, 1984.
4. Н. Вирт. Алгоритмы и структуры данных. – Досса, Хамарайан, 1997.
Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein,
Clifford (2001). "Section 24.3: Dijkstra’s algorithm". Introduction to
Algorithms (Second ed.). MIT Press and McGraw–Hill . pp. 595–601. ISBN 0-
262-03293-7 .
Dial, Robert B. (1969). "Algorithm 360: Shortest-path forest with
topological ordering [H]". Communications of the ACM . 12 (11): 632–
633. doi : 10.1145/363269.363610 .
Fredman, Michael Lawrence ; Tarjan, Robert E. (1984). Fibonacci heaps
and their uses in improved network optimization algorithms. 25th Annual
Symposium on Foundations of Computer Science. IEEE . pp. 338–
346. doi : 10.1109/SFCS.1984.715934 .
Fredman, Michael Lawrence ; Tarjan, Robert E. (1987). "Fibonacci heaps
and their uses in improved network optimization algorithms" . Journal of the
Association for Computing Machinery. 34 (3): 596–
615. doi : 10.1145/28869.28874 .
Zhan, F. Benjamin; Noon, Charles E. (February 1998). "Shortest Path
Algorithms: An Evaluation Using Real Road Networks". Transportation
Science . 32 (1): 65–73. doi : 10.1287/trsc.32.1.65 .
Leyzorek, M.; Gray, R. S.; Johnson, A. A.; Ladew, W. C.; Meaker, Jr., S.
R.; Petry, R. M.; Seitz, R. N. (1957). Investigation of Model Techniques — First](/data/documents/b731630c-7286-47f1-bfc3-5300c55023a9/page_37.png)
![Annual Report — 6 June 1956 — 1 July 1957 — A Study of Model Techniques
for Communication Systems. Cleveland, Ohio: Case Institute of Technology.
Knuth, D.E. (1977). "A Generalization of Dijkstra’s
Algorithm". Information Processing Letters . 6 (1): 1–5. doi : 10.1016/0020-
0190(77)90002-3 .
Ahuja, Ravindra K.; Mehlhorn, Kurt; Orlin, James B.; Tarjan, Robert E.
(April 1990). "Faster Algorithms for the Shortest Path Problem". Journal of the
ACM. 37 (2): 213–223. doi : 10.1145/77600.77615 .
Raman, Rajeev (1997). "Recent results on the single-source shortest paths
problem". SIGACT News. 28 (2): 81–87. doi : 10.1145/261342.261352 .
Thorup, Mikkel (2000). "On RAM priority Queues". SIAM Journal on
Computing. 30 (1): 86–109. doi : 10.1137/S0097539795288246 .
Thorup, Mikkel (1999). "Undirected single-source shortest paths with
positive integer weights in linear time" . journal of the ACM. 46 (3): 362–
394. doi : 10.1145/316542.316548 .](/data/documents/b731630c-7286-47f1-bfc3-5300c55023a9/page_38.png)
Mavzu: Deykstra Algoritmi. MUNDARIJA KIRISH ....................................................................................................................................................................................... 1.Graflar nazariyasining asosiy tushunchalari .......................................................................................................................... 2.Deykstra algoritmining paydo bo’lishi ................................................................................................................................... 3.Deykstra Algoritmi ................................................................................................................................................................ 4. Eng qisqa yo’llar masalalarining turlari .............................................................................................................................. 5.Deykstra algoritmning so’zli tavsifi ...................................................................................................................................... 6.Deykstra algoritmning C++ da kodi ..................................................................................................................................... 7.Tegishli muammolar va algoritmlar ..................................................................................................................................... Xulosa .................................................................................................................................................................................... Foydalangan adabiyotlar: .......................................................................................................................................................
KIRISH Qandaydir masalani xal etishga kirishishdan avval buning uchun eng yaxshi uslub izlanadi va uni qay tarzda tavsiflash aniqlanadi . Boshqacha qilib aytganda , biz doimo maqsadi ba ’ zi bir zaruriy natijaga erishishdan iborat , amallar ketma - ketligi bilan berilgan turli - tuman qoidalarga duch kelamiz . Bunday amallarning ketma - ketligi algoritm deb ataymiz . Matematikada algoritmning murakkabligi , xal etish masalalari va ularni ishlab chiqish prinsiplarini o ’ rganadigan maxsus “ Algoritmlar nazariyasi ” bo ’ limi xam mavjud . Algoritmlar nazariyasi – algoritmlarning umumiy xossalari , qonuniyatlari va ularni tasvirlanishining turli - tuman formal modellarini o ’ rganish bilan shug ’ ullanadi . Algoritm tushunchasini formallashtirish asosida ularning samaradorligi taqqoslash, ularning ekvivalentligi tekshirish, qo’llanilish sohasini aniqlash mumkin. Algoritm – berilgan natijaga erishish uchun qilinishi kerak bo lgan aniqʻ ko rsatmalar ketma-ketligi. Algoritm keng ma noda faqat kompyuterga oid ʻ ʼ atama bo’lmay, balki unda berilgan ko rsatmalarni bajara oluvchi har qanday ʻ narsaga oiddir. Algoritm, algoritm – ma lum bir turga oid masalalarni yechishda ʼ ishlatiladigan amallarning muayyan tartibda bajarilishi haqidagi aniq qoida (dastur). Kibernetika va matematikaning asosiy tushunchalaridan biri. O rta ʻ asrlarda o nli sanoq tizimi bo yicha to rt arifmetik amal bajariladigan qoidani ʻ ʻ ʻ Algaritm deb atashgan. "Bu qoidalarni matematikaga 9-asrda al-Xorazmiy tomonidan kiritilgan.
Ushbu kurs ishida biz graflar nima va Dijkstra algoritmi nima ekanligini o’rganamiz. Keyinchalik, biz Dijkstra algoritmi va uning c++ kodi misolini, tegishli chiqishi bilan birga o’rganamiz. Shuningdek, biz ushbu algoritmning real dunyoda amaliy qo’llanilishini yanada chuqurroq o’rganamiz. Shunday ekan, boshlaylik! 1.Graflar nazariyasining asosiy tushunchalari Graflar chiziqli bo’lmagan ma’lumotlar strukturasi bo’lib, u tugunlar va qirralarni o’z ichiga oladi. Tugunlar - bu cho’qqilar va qirralar - graflardagi ikkita tugunni bog’laydigan chiziqlar. Shuning uchun, graflarni tugunlarni bog’laydigan cho’qqilar to’plami va qirralarning to’plami sifatida aniqlash mumkin. Agar biz Facebook-ni graf deb hisoblasak, unda Facebook-dagi odamlar to’plami tugunlar deb hisoblanadi va ular orasidagi bog’liqlik chekkalar sifatida ko’rib chiqilishi mumkin. Shuning uchun, graflar elementlar juftligi orasidagi "bog’lanish" ni ko’rsatish uchun ishlatiladigan ma’lumotlar tuzilmalari. Quyidagi rasmda graflarning grafik tasviri ko’rsatilgan. Qirralari va uchlari bo’lgan grafga misol Umuman olganda, ikkita turdagi graflar mavjud: Yo’naltirilmagan graf: Yo’naltirilmagan grafdan foydalanib, har bir bog’langan tugun juftligi uchun siz bir tugundan ikkinchisiga har ikki yo’nalishda ham o’tishingiz mumkin. Uchlar Qirra
Yo’naltirilgan graf: Yo’naltirilgan graf yordamida siz har bir bog’langan tugun juftligi uchun faqat ma’lum bir yo’nalishda bir tugundan ikkinchisiga o’tishingiz mumkin. Ikki tugunni birlashtiruvchi chekka sifatida o’qlardan foydalanishingiz mumkin. Bundan tashqari, vaznli graf - bu o’ziga xos "og’irlik" yoki "xarajat" ga ega bo’lgan qirralardan tashkil topgan graf. Biron bir og’irligini, vaqtni, masofani yoki juftlik tugunlari o’rtasidagi "bog’lanish" ni modellashtiradigan har qanday narsani ifodalashi mumkin. 2.Deykstra algoritmining paydo bo’lishi Rotterdamdan Groningenga umuman olganda berilgan shahardan ushbu shahargacha sayohat qilishning eng qisqa yo’li nima? Bu yigirma daqiqada mo’ljallangan eng qisqa yo’l uchun algoritm. Bir kuni ertalab men yosh yigitlar bilan Amsterdamda xarid qilardim va charchagan edik, biz kofe choy ichib, kofe terastasiga o’tirdik va men buni qila olamanmi yoki yo’qmi deb o’ylagandim va keyinchalik eng qisqa yo’l uchun algoritmni yaratdim. Men aytganimdek, yigirma daqiqalik ixtiro bo’ldi. Darhaqiqat, u 59 yil ichida, uch yil o’tib nashr etildi. Bu kitob hali ham o’qilishi mumkin, aslida juda yaxshi. Bu juda yaxshi bo’lgan sabablardan biri men uni qalam va qog’ozsiz tasvirladim. Keyinchalik bilib oldimki, qalam va qog’ozsiz loyihalashtirishning afzalliklaridan biri deyarli barcha oldini olish mumkin bo’lgan murakkabliklardan qochishingiz kerak ekan. Oxir-oqibat, bu algoritm mening shon-shuhratimning asosiy toshlaridan biri bo’lgan. Dijkstra 1956 yilda Amsterdamdagi Matematik markazda ARMAC nomli yangi kompyuterning imkoniyatlarini namoyish etish uchun dasturchi sifatida eng qisqa yo’l muammosini o’ylab topdi. Uning maqsadi ham hisoblanmaydigan odamlar tushunishi mumkin bo’lgan muammoni va echimni (kompyuter tomonidan ishlab chiqariladigan) tanlash edi. U eng qisqa yo’l algoritmini ishlab chiqdi va undan keyin uni Gollandiyada 64 ta shaharning biroz soddalashtirilgan transport xaritasi uchun ARMAC uchun amalga oshirdi (64,ya’ni 6 bit shahar
raqamini kodlash uchun etarli bo’ladi). Bir yil o’tgach, u institutning navbatdagi kompyuterida ishlaydigan apparat-muhandislardan boshqa muammolarga duch keldi: mashinaning orqa panelidagi pimlarni ulash uchun zarur bo’lgan simni kamaytirish. Yechim sifatida u Primning eng kichik spanning daraxt algoritmi deb nomlanadigan algoritmni (avvalroq Jarnikka ma’lum va shuningdek, Primni qayta kashf qilgan) kashf etdi. Dijkstra 1959 yilda, Primdan ikki yil keyin va Jarnikdan 29 yil o’tgach algoritmi nashr etdi. Gollandiyalik olim Edsger Deykstra algoritmi grafning boshlang’ich berilgan tugunidan boshlab qolgan barcha tugunlargacha bo’lgan barcha eng qisqa yo’llarni topadi. Uning yordamida, agar barcha zarur ma’lumotlar berilgan bo’lsa, masalan, neft va shu kabi mahsulotlarni eksport qilish uchun bitta shahardan boshqa shaharlarning har biriga borish uchun qaysi yo’llar ketma- ketligini tanlash afzalroq ekanligini bilib olish mumkin. Ushbu usulning salbiy tomoni shundaki, manfiy vaznga ega bo’lgan qirralari mavjud bo’lgan graflarni qayta ishlash imkonining mavjud emasligi, ya’ni, masalan, ba’zi tizim birorta kompaniya uchun foydasiz bo’lgan marshrutlarni taqdim qilsa, u holda u bilan ishlash uchun Dijkstraning algoritmidan foydalanib bo’lmaydi. Algoritmni dasturiy ta’minotini amalga oshirish uchun ikkita massiv kerak bo’ladi: mantiqiy toifadagi visited - tashrif buyurilgan tugunlar haqidagi ma’lumotlarni saqlash uchun va topilgan eng qisqa yo’llar kiritiladigan butun toifadagi - distance. G= {V, E} graf berilgan bo’lsin. V to’plamga tegishli barcha tugunlar dastlab tashrif buyurilmagan deb belgilanadi, ya’ni visited massivining elementlariga false qiymat berib chiqiladi. Eng afzal yo’lni topish masalasi qaralyapti. Distance massivining har bir elementiga shunday qiymat beriladiki, ixtiyoriy potensial yo’ldan katta bo’lsin (odatda, bu qiymatni cheksiz katta qiymat deb qaraladi, ammo dasturda berilgan toifaning qiymatlar diapazonidagi eng katta qiymat sifatida olinadi). Boshlang’ich nuqta sifatida s tugun tanlanadi va unga nol yo’l belgilanadi: distance [s] = 0, chunki s-dan s- gacha hech qanday qirra yo’q (bu usulda ilmoqlar qaralmaydi).