logo

Deykstra Algoritmi

Загружено в:

12.08.2023

Скачано:

0

Размер:

1049.7021484375 KB
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).   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. 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. 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. 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. 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. 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  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. 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. 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 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 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. 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 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 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.                                                                                                                 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.   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} 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. 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} 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. 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ʻ ʻ "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. 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 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: 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 ++ )
    {         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 },         { 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 ; 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 ++ )                       
     {            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 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 usuli   Dijkstra   algoritmining   uchburchak   meshidagi   geodezial   masofani
hisoblaydigan uzluksiz versiyasidir. 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.
    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 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 .

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).