logo

Eng qisqa masofani toppish. Deykstra algoritmi va uni tahlil qilish.

Загружено в:

12.08.2023

Скачано:

0

Размер:

1774.8564453125 KB
Mavzu: Eng qisqa masofani toppish. Deykstra algoritmi va uni tahlil qilish.
Reja:
1 . Kirish .
2. Asosiy qisim
1. Eng qisqa yo’llar masalalarining turlari.
2. Deykstra algoritmning so’zli tavsifi
3. Masalaning qo’yilishi.
4. Deysktra algoritmi.
3 .  Xulosa.
4. Foydalanilgan 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.
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.   Oxir-oqibat,
bu algoritm mening shon-shuhratimning asosiy toshlaridan biri bo'lgan.
- Edzger Dijkstra, ACM bilan aloqa, Philip L. Frana, 2001.
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.
1.  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   irralar   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 ,   turdagi   har   bir
uchlar juftliklari orasida va boshqalar.
2. Deykstra algoritmning so’zli tavsifi
Eng   qisqa   masofani   topish   masalalarni   yechish   uchun   Deykstra   algoritmi   ancha
qulay va yahshi deb topilgan.
Algoritm quyidagi qa damlardan iborat:  
1.
Dastlab,   berilgan   (Lex)   uchidan   qolgan   barcha   uchlargacha   bir   qirra   uzunligidagi
masofalar aniqlanadi.  
2.
Ulardan   eng   qisqasi   “doimiy   eng   qisqa   masofa”   sifatida   belgilanadi
(Lex   va   BVa   uchlari qirrasi).  
3.
Aniqlangan masofa   BVa   dan boshqa bor uchlargacha masofalarga qo’shiladi.  
4.
Hosil   bo’lgan   yig’indilar   dastlab   aniqlangan   Lex   dan   qolgan   uchlargacha   bo’lgan
masofalar   bilan   taqqoslanadi.   Natijada   masofasi   qisqaroq   bo’lgan   uchning   qirrasi
tanlanadi.  
5.
BVa   uchi,   eng   qisqa   masofa   aniqlangan   uch   sifatida,   ruyhatdan   o’chiriladi. Ruyhatga   boshqa   uch   qo’yiladi,   masalan,   Roa.   Bva   o’z   navbatida,   boshqa,
izlanayotgan ruyhatga qo’yiladi.  
Keyingi eng qisqa masofani topish uchun butun jarayon qayta bajariladi.   BVa   dan
keyin   yana   bir   uch   ruyhatga   qo’yiladi.   Dastlabkisi   esa   ruyhatdan   o’chiriladi.
Sikl   Bed   va   Lex   uchlarini   bog’lash   uchun   belgilangan   qirralar   aniqlanishi   bilan
to’xtatiladi.
3. Deyskra   Algoritmi.
Grafdagi   eng   qisqa   marshrutlar   uchun   ko'plab   qidiruv   algoritmlari   bo'yicha,
Habreda   faqatgina   Floyd-Worschall   algoritmining   ta'rifi   topildi.   Ushbu   algoritm
grafikaning   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   grafikning   boshqa   vertikalari   orasida   topadi.   Ushbu
algoritmning   nochorligi,   agar   grafika   salbiy   og'irliklarga   ega   bo'lsa,   u   noto'g'ri
ishlaydi.
Misol uchun, G quyidagi ko'rsatgichni bajaring:
tasvirUshbu   grafikani   matritsa   sifatida   taqdim   etamiz:tasvir
Keling,   vertex   1ni   manba   sifatida   qabul   qilaylik,   shuning   uchun   vertex   1dan   eng
kichkina marshrutlarni 2, 3, 4 va 5-ustungacha topamiz.Ushbu algoritm grafaning
barcha   verticesida   yineleyadi   va   manba   verteksidan   muayyan   vertexga   ma'lum
minimal   masofa   bo'lgan   belgilarga   ularni   belgilaydi.   Masalan,   ushbu   algoritmni
ko'rib   chiqaylik.Keling,   1   tepalikka   tegni   0   ga   teng   qilamiz,   chunki   bu   vertex
manba hisoblanadi. Qolgan tepaliklar abadiylikka teng teglar bilan belgilanadi.
Keyinchalik, minimal yorlig'i (hozirda vertex 1) bo'lgan vertikal W ni tanlang
va   vertex   W   dan   mediatorlar   vertikalarini   o'z   ichiga   olmaydi.   W   belgisining
yig'indisiga teng bo'lgan belgini va hisobga olingan vertikalarning har biriga qarab,
Vdan vertikaga yo'llarni belgilang, lekin natijada faqat oldingi qiymatdan kamroq
bo'lsa.   Agar   bu   miqdor   kam   bo'lmasa,   oldingi   belgini   o'zgartirmang.Biz   W   dan
to'g'ridan-to'g'ri   yo'lni   egallagan   barcha   vertikalarni   ko'rib   chiqdik,   keyin   V   ga
tashrif   buyurib,   tepaligini   eng   past   qiymatga   ega   bo'lganlardan   tanlaymiz   va   u
keyingi V tepasida bo'ladi. Bu holda, bu birinchi 2 yoki 5. Agar bir xil teglar bilan
bir   necha   vertikalar   mavjud   bo'lsa,   ularning   qaysi   biri   W   ni   tanlashimiz   muhim
emas.
Biz vertex 2 ni tanlaymiz. Biroq, undan bitta chiqish yo'li yo'q, shuning uchun
darhol   ushbu   vertexni   tashrif   buyurgan   deb   belgilab   olamiz   va   keyingi   vertikaga
minimal belgisi bilan kiramiz. Bu safar faqat vertex 5da eng kam belgilar mavjud.
5-dan   5-gacha   to'g'ridan-to'g'ri   yo'llar   mavjud   bo'lgan   barcha   vertikalarni   ko'rib chiqing,   ammo   hozircha   ular   tashrif   buyurilgan   deb   bo'lmaydi.   Shunga   qaramay ,
vertex W yorlig'ining yig'indisi  va W dan joriy vertexning chekkasini  topamiz va
agar bu summa oldingi yorliqdan kamroq bo'lsa, biz natijada olingan qiymat bilan
etiketaning qiymatini o'zgartiramiz.
Rasmga asoslanib, biz uchinchi va to'rtinchi zirvalarning yorliqlari kichikroq
ekanligini, ya'ni manba tepasidagi bu tepaliklarga nisbatan qisqaroq yo'lni topdik.
Keyinchalik, 5 vertexni tashrif buyurgan deb belgilang va eng past belgisi bo'lgan
keyingi   vertikani   tanlang.   Yuqorida   keltirilgan   barcha   harakatlar   takrorlanmagan
vertikalar mavjud ekan, takrorlang.
Barcha   amallarni   bajarib   bo'lgach,   biz   quyidagi   natijani   qo'lga   kiritamiz:
Dijkstra algoritmi
Grafikdagi   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   grafika
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 grafikalar 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 grafikalar 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   Ygacha   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   abadiyatga   sozlang.
Boshlang'ich   tugunni   dolzarb   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 Agacha masofa  6 + 2 = 8 bo'ladi.
Agar   B   ilgari   belgilangan   bo'lsa,   8dan   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 grafika hisoblanadi.
Bir shahar  xaritasida ikkita kavşak  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   abadiylik   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.   Shu   bilan   birga,   u   algoritmning   zaif   tomonlaridan   birini   ham   ko'rsatishi
mumkin: ba'zi bir topologiyalardagi nisbiy sekinligi.
Dastur kodi
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   manbaeng   qisqa   yo ' lni   o ' qiy   olishimiz   mumkin :
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.
2//boshlash.
8//V manbadan tortib v. Ga noma'lum masofa.
9//Predessori v.
14//Asosiy ko'chadan.
15//Eng yaxshi vertexni olib tashlang.
16//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
// The program is for adjacency matrix representation of the graph #include
#include
// Number of vertices in the graph
#define V 9
// A utility function to find the vertex with minimum distance value, from
// the set of vertices not yet included   in shortest path tree
int minDistance(int dist[], bool sptSet[])
{
// Initialize min value
int   min   =   INT_MAX,   min_index;
for (int v = 0; v < V; v++)
if (sptSet[v] == false && dist[v] <= min)
min = dist[v], min_index = v;
return min_index; }
// A utility function to print the constructed distance array
int printSolution(int dist[], int n)
{
printf("Vertex Distance from Source\n");
for (int i = 0; i < V; i++)
printf("%d tt %d\n", i, dist[i]);
}
// Function that implements Dijkstra's single source shortest path algorithm // for a graph represented using adjacency matrix representation
void dijkstra(int graph[V][V], int src)
{ int dist[V]; // The output array. dist[i] will hold the shortest
//   distance from src to i
bool sptSet[V]; // sptSet[i] will be true if vertex i is included in shortest
// path tree or shortest distance from src to i is finalized
// Initialize all distances as INFINITE and stpSet[] as false
for (int i = 0; i < V; i++)
dist[i] = INT_MAX, sptSet[i] = false;
// Distance of source vertex from itself is always 0
dist[src] = 0; // Find shortest path for all vertices
for (int count = 0; count < V-1; count++)
{
// Pick the minimum distance vertex from the set of vertices not
// yet processed. u is always equal to src in the first iteration.
int u = minDistance(dist, sptSet);
// Mark the   picked vertex as processed
sptSet[u] = true;
// Update dist value of the adjacent vertices of the picked vertex.
for (int v = 0; v < V; v++)
// Update dist[v] only if is not in sptSet, there is an edge from
// u to v, and total weight of path from src to v through u is // smaller than current value of dist[v]
if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX
&& dist[u]+graph[u][v] < dist[v])
dist[v] = dist[u] + graph[u][v];
}
// print the constructed distance array
printSolution(dist, V);
}
// driver program to test above function
int main()
{
/* Let us create the example graph discussed above */
int graph[V][V] = {{0, 4, 0, 0, 0, 0, 0, 8, 0},
{4, 0, 8, 0, 0, 0, 0, 11, 0},
{0, 8, 0, 7, 0, 4, 0, 0, 2},
{0, 0, 7, 0, 9, 14, 0, 0, 0},
{0, 0, 0, 9, 0, 10, 0, 0, 0},
{0, 0, 4, 14, 10, 0, 2, 0, 0},
{0, 0, 0, 0, 0, 2, 0, 1, 6},
{8, 11, 0, 0, 0, 0, 1, 0, 7},
{0, 0, 2, 0, 0, 0, 6, 7, 0} };
dijkstra(graph, 0);
return 0;
}
2-ko’rinish:
#include
#include   /*Used for INT_MAX*/
using   namespace std ;
#define vertex 7 /*It is the total no of verteices in the graph*/
int   minimumDist(int   dist[],   bool   Dset[])   /*A   method   to   find   the   vertex   with
minimum distance which is not yet included in Dset*/
{
int min=INT_MAX,index; /*initialize min with the maximum possible value
as infinity does not exist */
for(int   v=0;v<=""   p=""   style="color:   rgb(0,   0,   0);   font-family:   "Times   New
Roman";   font-size:   16px;   font-style:   normal;   font-variant-ligatures:   normal;   font-
variant-caps:   normal;   font-weight:   400;   letter-spacing:   normal;   orphans:   2;   text-
align:   start;   text-indent:   0px;   text-transform:   none;   white-space:   normal;   widows:
2;   word-spacing:   0px;   -webkit-text-stroke-width:   0px;   text-decoration-thickness:
initial; text-decoration-style: initial; text-decoration-color: initial;">
{
if(Dset[v]==false && dist[v]<=min)
{
min=dist[v];
index=v;
} }
return index;
{
int dist[vertex];
bool Dset[vertex];
for(int i=0;i<="" p="">
{
dist[i]=INT_MAX;
Dset[i]=false;
}
dist[src]=0; /*Initialize the distance of the source vertec to zero*/
for(int c=0;c<="" p="">
{
int   u=minimumDist(dist,Dset);   /*u   is   any   vertex   that   is   not   yet   included   in
Dset and has minimum distance*/
Dset[u]=true; /*If the vertex with minimum distance found include it to Dset*/
for(int v=0;v<="" p="">
/*Update dist[v] if not in Dset and their is a path from src to v through u that 
has distance minimum than current value of dist[v]*/
{
if(!Dset[v] && graph[u][v] && dist[u]!=INT_MAX && dist[u]+graph[u]
[v]<dist[v])< p="">
dist[v]=dist[u]+graph[u][v];</dist[v])<> }
}
cout<<"Vertex\t\tDistance from source"<<="" p="">
for(int i=0;i<="" p="">
{
char c=65+i;
cout<<c<<"\t\t"<<dist[i]<<="" p="">
}
}
int main()
{
int graph[vertex][vertex]={{0,5,3,0,0,0,0},{0,0,2,0,3,0,1},{0,0,0,7,7,0,0},
{2,0,0,0,0,6,0},{0,0,0,2,0,1,0},{0,0,0,0,0,0,0},
{0,0,0,0,1,0,0}};
dijkstra(graph,0);
return 0;
}
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   grafikka
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   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   grafika   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.
Eng qisqa masofani   toppishga doir testlar
ifoda   kiymatini   xisoblash   uchun   keltirilgan   shartli   operatorlardan   kaysi   biri   tugri?  
  A)   Keltirilgan   operatorlardan   xech   biri   berilgan   ifodani   tugri   xisoblamaydi.      
B)   If   y<0   then   Begin   x<0   then   N:=3   else   N:=4End      
        else   If   x<0   then   N:=2   else   N:=1;    
C)   If   (y>=0)   and   (x>=0)   then   N:=1   else   N:=2;      
        If   (y<0)   and   (x<0)   then   N:=3   else   N:=4;    
D)   If   x<0   then   Begin   y<0   then   N:=1   else   N:=2   End      
        else   Begin   If   y>=0   then   N:=3   else   N:=4   End   ;    
5.     Ta’minlash   operatori   kanday   ishni   bajarish   uchun   muljallangan?   Eng   umumiy   j
avobni   toping.  
A)     Operatorning     ung     kismida     turgan         ifodani     xisoblaydi     va     uning     kiymatini     chap    
kismdagi   uzgaruvchiga   ta’minlaydi.      
B)   Uzgaruvchilarga   kiymat   ta’minlaydi.    
C)   Uzgaruvchilarning   turini   boshkasiga   uzgartiradi.    
D)   Ifoda   qiymati   qaysi   turga   mansubligini   aniqlaydi.      
Deykstra   algoritmi   yordamida   ikkita   tepalik   orasidagi   eng   qisqa
masofani topish
CD   (CXDX,   C2D2)   nuqta   sifatida   tasvirlangan   C5   \u003d   D5   A5V5   teng
darajada ...
IKKI PARALLEL TEKISLIK ORASIDAGI MASOFANI ANIQLASH
Umumiy holatdagi ikkita parallel tekislik orasidagi  masofani aniqlash 01 | X
uni   proektorlarning   holatiga   aylangan   bir   xil   ikkita   samolyot   orasidagi   masofani
aniqlash   vazifasiga   qisqartirish   qulay.   Bunday   holda,   tekisliklar   orasidagi   masofa
to'g'ri chiziqlar orasidagi perpendikulyar, ...
IKKITA KESIB O'TGAN TO'G'RI CHIZIQLAR ORASIDAGI MASOFANI
ANIQLASH
Agar   siz   ikkita   kesish   chizig'i   orasidagi   eng   qisqa   masofani   aniqlashingiz
kerak   bo'lsa,   proektsion   tekisliklarning   tizimlarini   ikki   marta   o'zgartirishingiz
kerak.   Ushbu   muammoni   hal   qilishda   to'g'ri   chiziq   CD   (CXDX,   C2D2)   nuqta
sifatida   tasvirlangan   C5   \u003d   D5   (rasm   198).   Ushbu   nuqtadan   proektsiyagacha
bo'lgan masofa A5V5 teng darajada ...
IKKITA KESIB O'TGAN TO'G'RI CHIZIQLAR ORASIDAGI BURCHAK
Bu ma'lumotlarga parallel ravishda ikkita kesishgan chiziq orasidagi burchak.
Shunday   qilib,   bu   vazifa   oldingisiga   o'xshashdir.   Uni   hal   qilish   uchun
o'zboshimchalik bilan nuqta olish va u orqali berilgan kesishgan to'g'ri chiziqlarga
parallel   ravishda   ikkita   to'g'ri   chiziq   chizish   kerak   va   proyeksiyalarning
konvertatsiyasidan foydalanib kerakli burchakni aniqlang ...
IKKALA   PARALLEL   TO'G'RI   CHIZIQLAR   ORASIDAGI   MASOFANI
ANIQLASH
Muammo   proektsion   tekisliklarni   ikki   marta   almashtirish   bilan   hal   qilinadi.
Oxirgi   bosqichda   proyeksiya   tekisliklaridan   biri   kesishgan   chiziqlardan   biriga
perpendikulyar   bo'lishi   kerak.   Keyin   ular   orasidagi   eng   qisqa   masofa
perpendikulyar   segmentning   boshqa   kesishish   chizig'iga   kattaligi   bilan
aniqlanadi .... Dijkstra algoritmi  -  bu Gollandiyalik olim  Edsger  Deykstra  tomonidan  1959
yilda ixtiro qilingan grafik asosidagi algoritm. Grafika tepalaridan birining qolgan
qismiga qadar eng qisqa yo'llarni topadi. Algoritm ishlaydi faqat salbiy og'irlikdagi
chekkalari bo'lmagan grafikalar uchun.
1-chi tepalikdan boshqalarga qadar eng qisqa masofani topish talab etilsin.
Aylanalar   tepaliklarni,   chiziqlar   ular   orasidagi   yo'llarni   (grafik   qirralarini)
bildiradi.   Tepaliklarning   raqamlari   doiralarda   ko'rsatilgan,   ularning   "narxi"
qirralarning yuqorisida - yo'lning uzunligi ko'rsatilgan. Har bir tepalik yonida qizil
yorliq bor - bu tepalikka 1-tepalikdan eng qisqa yo'l uzunligi.
Birinchi   qadam ...   Keling,   misolimiz   uchun   Dijkstra   algoritmining   bir
bosqichini ko'rib chiqaylik. 1 tepada minimal yorliq bor, uning qo'shnilari - 2, 3 va
6 tepaliklar.
Birinchi   navbatda   birinchi   vertikalning   qo'shnisi   vertex   2,   chunki   unga   yo'l
uzunligi   minimaldir.   Unga   1-vertikal   orqali   o'tadigan   yo'l   uzunligi   1-vertikal
yorlig'i qiymati va 1-dan 2-gacha bo'lgan chekka uzunligi yig'indisiga teng, ya'ni 0
+ 7 \u003d 7. 2-vertexning amaldagi yorlig'idan kam, abadiylik, shuning uchun 2-
chi tepaliklarning yangi yorlig'i 7 ga teng.
Biz xuddi shunday operatsiyani 1-chi vertikalning boshqa ikkita qo'shnisi - 3-
chi va 6-chi bilan bajaramiz.
1   vertexning   barcha   qo'shnilari   tekshiriladi.   1-cho'qqiga   qadar   bo'lgan
minimal   minimal   masofa   yakuniy   hisoblanadi   va   qayta   ko'rib   chiqilmaydi   (bu
haqiqatan   ham   shunday   ekanligini   birinchi   bo'lib   E.   Deykstra   isbotlagan).   Ushbu
tepaga tashrif buyurganligini belgilash uchun uni grafikadan o'chirib tashlaymiz.
Ikkinchi   qadam ...   Algoritm   bosqichi   takrorlanadi.   Qayta   ko'rilmagan
tepaliklarning "eng yaqinini" yana toping. Bu vertikal 2, 7 bilan belgilangan.
Biz yana tanlangan tepalik qo'shnilarining yorliqlarini kamaytirishga harakat
qilamiz, ularga 2-tepalikdan o'tishga harakat qilamiz. 2 tepalikning qo'shnilari 1, 3
va 4 tepaliklaridir.
2   vertexning   birinchi   (tartibda)   qo'shnisi   -   vertex   1.   Ammo   u   allaqachon
tashrif buyurgan, shuning uchun biz 1-vertex bilan hech narsa qilmaymiz.
2-vertexning   keyingi   qo'shnisi   3-vertexdir,   chunki   u   tepaliklarning   minimal
yorlig'iga tashrif buyurilmagan deb belgilangan. Agar siz unga 2 orqali kirsangiz,
unda   bunday   yo'lning   uzunligi   17   ga   teng   bo'ladi   (7   +   10   \u003d   17).   Ammo
uchinchi   tepalikning   amaldagi   yorlig'i   9   ga   teng,   bu   17   dan   kam,   shuning   uchun
yorliq o'zgarmaydi. 2-vertexning   yana   bir   qo'shnisi   -   4-vertex.   Agar   siz   unga   2-chi   orqali
borsangiz, u holda bunday yo'lning uzunligi 2-chi tepaga eng qisqa masofa va 2 va
4-tepalar orasidagi masofaning yig'indisiga teng bo'ladi, ya'ni , 22 (7 + 15 \u003d
22) ... 22 yildan beri<,  устанавливаем   метку   вершины  4  равной  22.
Barcha   vertex   2-ning   barcha   qo'shnilari   ko'rib   chiqildi,   masofani   muzlatib
qo'ying va tashrif buyurganingiz kabi belgilang.
Uchinchi   qadam ...  Biz  vertikal   3  ni   tanlab  algoritm  qadamini   takrorlaymiz.
"Qayta ishlash" dan so'ng biz quyidagi natijalarga erishamiz:
Keyingi   qadamlar ...   Qolgan   tepaliklar   uchun   algoritm   qadamini
takrorlaymiz. Bu navbati bilan 6, 4 va 5 tepaliklar bo'ladi.
Algoritm bajarilishini yakunlash ... Algoritm endi tepaliklarni qayta ishlash
imkoni   bo'lmaganda   o'z   ishini   tugatadi.   Ushbu   misolda   barcha   tepaliklar   chizib
tashlangan,   ammo   har   qanday   misolda   shunday   bo'ladi   deb   ishonish   xato   -   ba'zi
cho'qqilar   ularga   etib   borolmasa,   ya'ni   grafikani   uzib   qo'ygan   bo'lsa,   ularni   kesib
o'tmasdan   qolishi   mumkin.   Algoritm   natijasini   oxirgi   rasmda   ko'rish   mumkin:
1dan 2 gacha bo'lgan eng qisqa yo'l 7 ga, 3 ga 9 ga, 4 ga 20 ga, 5 ga 20 ga, 6 ga 11
ga teng.
Algoritmni turli dasturlash tillarida amalga oshirish:
C ++
#include  "stdafx.h"  #include   std  nom  maydonidan  foydalanish;  const  int   V  \
u003d  6;   //   Dijkstra   algoritmi   bekor   Dijkstra  (int   GR   [V]   [V],   int   st)   (int   masofa
[V], hisoblash,  indeks,  i, u, m \u003d st  + 1;  bool  tashrif  buyurdi  [V];  uchun (i  \
u003d   0;   i   <="min)"   index="i;"   u="index;"   visited[u]="true;"   gr[u][i]=""
distance[u]!="INT_MAX"   distance[u]+gr[u][i]<<" Стоимость =""   пути =""   из =""
начальной =""   вершины =""   до =""   остальных :\t\n";=""   (distance[i]!
="INT_MAX)"   cout<<m<<"=""   style="box-sizing:   inherit;">"<<i+1<<"   ==""
"<<distance[i]<<<m<<"=""   style="box-sizing:   inherit;">   "<<i+1<<"   ==""
"<<" маршрут =""   недоступен "<<<" Начальная =""   вершина =""   style="box-
sizing:   inherit;">\u003e   ";   cin   \u003e\u003e   start;   Dijkstra   (GR,   start-1);   tizim   ("
pauza \u003e\u003e bekor ");)
PASKAL
dastur   DijkstraAlgoritm;   crt   dan   foydalanadi;   const   V   \u003d   6;   inf   \u003d
100000; vektor turi \u003d butun sonli massiv; var start: integer; const GR: butun
sonli massiv \u003d ((0, 1, 4, 0, 2, 0), (0, 0, 0, 9, 0, 0), (4, 0, 0, 7, 0, 0), (0, 9, 7, 0,
0, 2), (0, 0, 0, 0, 0, 8), (0, 0, 0, 0, 0, 0)); (Dijkstra algoritmi) protsedurasi Dijkstra
(GR:   integer   array;   st:   integer);   var   count,   index,   i,   u,   m,   min:   integer;   masofa:
vektor; tashrif buyurgan: mantiqiy qator; boshlang m: \u003d st; i: \u003d 1 dan V gacha   bo'lgan   masofa   boshlanadi   [i]:   \u003d   inf;   tashrif   buyurilgan   [i]:   \u003d
noto'g'ri; oxiri; masofa: \u003d 0; hisoblash uchun: \u003d 1 dan V-1 gacha min: \
u003d   inf;   uchun   i:   \u003d   1   dan   V   gacha,   agar   (tashrif   buyurilmagan   [i])   va
(masofa   [i])<=min)   then   begin   min:=distance[i];   index:=i;   end;   u:=index;
visited[u]:=true;   for   i:=1   to   V   do   if   (not   visited[i])   and   (GR<>0)   va   (masofa
[u]<>inf)   va   (masofa   [u]   +   GR   <=""   style="box-sizing:   inherit;">inf   then   writeln
(m,   "\u003e",   i,   "\u003d",   masofa   [i])   else   Writeln   (m,   "\u003e",   i,   "\u003d",
"marshrut mavjud emas"); oxiri; (asosiy dastur bloki) boshlash clrscr; write ("Start
vertex \u003e\u003e"); o'qish (boshlash); Dijkstra (GR, start); oxiri.
JAVA
import   java.io.BufferedReader;   import   java.io.IOException;   import
java.io.InputStreamReader;   import   java.io.PrintWriter;   import   java.util.ArrayList;
import   java.util.Arrays;   import   java.util.StringTokenizer;   public   class   Solution
(private static int INF \u003d Integer.MAX_VALUE / 2; private int n; // digraph in
the   vertices   of   the   number   of   private   int   m;   //   digray   in   the   digraph   in   private
ArrayList   adj;   //   qo'shni   ro'yxat   xususiy   ArrayList   vazn;   //   ishlatiladigan   maxsus
boolean   digrafidagi   chekka   og'irligi;   //   o'tgan   va   o'tmagan   tepalar   haqida
ma'lumotni saqlash uchun massiv xususiy int dist; // boshlang'ich tepadan masofani
saqlash uchun massiv // boshlang'ich tepadan eng qisqa yo'lni tiklash uchun zarur
bo'lgan   ajdodlar   qatori   private   int   pred;   int   start;   //   boshlang'ich   tepalik,   undan
boshqalarga masofa xususiy BufferedReader cin; xususiy PrintWriter cout; xususiy
StringTokenizer   tokenizer;   //   Dijkstra   algoritmini   boshlang'ich   tepadan   xususiy
void dejkstra (int s) dan boshlash tartibi (dist [s] \u003d 0; // boshlang'ich tepalikka
eng qisqa masofa 0 uchun (int iter \u003d 0; iter)< n; ++iter) { int v = -1; int distV
=   INF;   // выбираем   вершину ,   кратчайшее   расстояние   до   которого   еще   не
найдено   for   (int   i  =  0;  i   <  n;  ++i)  {  if   (used[i])  {  continue;   } if  (distV  < dist[i])
{   continue;   }   v   =   i;   distV   =   dist[i];   }   // рассматриваем   все   дуги ,   исходящие   из
найденной   вершины  for (int i = 0; i < adj[v].size(); ++i) { int u = adj[v].get(i); int
weightU   =   weight[v].get(i);   // релаксация   вершины   if   ( dist [ v ]   +   weightU   <
dist [ u ])   {   dist [ u ]   =   dist [ v ]   +   weightU ;   pred [ u ]   =   v ;   }   }   //помечаем   вершину   v
просмотренной,   до   нее   найдено   кратчайшее   расстояние   used [ v ]   =   true ;   }   }
//процедура   считывания   входных   данных   с   консоли   private   void   readData ()
throws   IOException   {   cin   =   new   BufferedReader ( new
InputStreamReader ( System . in ));   cout   =   new   PrintWriter ( System . out );   tokenizer   =
new   StringTokenizer ( cin . readLine ());   n   =
Integer . parseInt ( tokenizer . nextToken ());   //считываем   количество   вершин   графа
m   =   Integer . parseInt ( tokenizer . nextToken ());   //считываем   количество   ребер
графа   start   =   Integer . parseInt ( tokenizer . nextToken ())   -   1;   //инициализируем
списка смежности графа размерности   n   adj   =   new   ArrayList [ n ];   for   ( int   i   = 0;   i
<   n ;   ++ i )   {   adj [ i ]   =   new   ArrayList ();   )   //   qirralarning   og ' irliklari   saqlanadigan
ro ' yxatning   boshlanishi   \ u 003 d   yangi   ArrayList   [ n ];   uchun   ( int   i   \ u 003 d   0;   i <   n ; +
+ i ) {  weight [ i ] =  new   ArrayList (); ) // ( int   i  \ u 003 d  0;   i   uchun   qirralarning   ro ' yxati
bilan   belgilangan   grafikani   o ' qing <   m ;   ++ i )   {   tokenizer   =   new StringTokenizer ( cin . readLine ());   int   u   =   Integer . parseInt ( tokenizer . nextToken ());
int   v   =   Integer . parseInt ( tokenizer . nextToken ());   int   w   =
Integer . parseInt ( tokenizer . nextToken ());   u --;   v --;   adj [ u ]. add ( v );
weight [ u ]. add ( w );   }   used   =   new   boolean [ n ];   Arrays . fill ( used ,   false );   pred   =   new
int [ n ];  Arrays . fill ( pred , -1);  dist  =  new   int [ n ];  Arrays . fill ( dist ,  INF ); } //процедура
восстановления кратчайшего пути по массиву предком   void   printWay ( int   v ) {
if  ( v  == -1) { return; } printWay(pred[v]); cout.print((v + 1) + " "); } //процедура
вывода данных в консоль private void printData() throws IOException { for (int
v   =   0;   v   <   n;   ++v)   {   if   (dist[v]   !=   INF)   {   cout.print(dist[v]   +   "   ");   }   else
{ cout.print("-1 "); } } cout.println(); for (int v = 0; v < n; ++v) { cout.print((v + 1)
+   ":   ");   if   (dist[v]   !=   INF)   {   printWay(v);   }   cout.println();   }   cin.close();
cout.close(); } private void run() throws IOException { readData(); dejkstra(start);
printData(); cin.close(); cout.close(); } public static void main(String args) throws
IOException { Solution solution = new Solution(); solution.run(); } }
Boshqa variant:
Import   java.io.   *;   import   java.util.   *;   umumiy   sinf   Dijkstra   (xususiy   statik
yakuniy   Graph.Edge   GRAPH   \u003d   (yangi   Graph.Edge   ("a",   "b",   7),   yangi
Graph.Edge ("a", "c", 9)), yangi Graph.Edge ( "a", "f", 14), yangi Graph.Edge ("b",
"c", 10), yangi Graph.Edge ("b", "d", 15), yangi Graph.Edge ("c" "," d ", 11), yangi
Graph.Edge (" c "," f ", 2), yangi Graph.Edge (" d "," e ", 6), yangi Graph.Edge (" e
",   "f",   9),);   xususiy   statik   yakuniy   String   START   \u003d   "a";   xususiy   statik
yakuniy String END \u003d "e"; public static void main (String arggs) (Grafik g \
u003d   yangi   Grafika   (GRAPH);   g.dijkstra   (START);   g.printPath   (END);
//g.printAllPaths   ();))   sinf   Grafigi   (shaxsiy   yakuniy   xarita   grafik;   //   Edge
to'plamidan   qurilgan   vertex   moslamalariga   vertex   nomlarini   xaritalash   /   **
Grafikning  bir   qirrasi   (faqat   Graf   konstruktori  foydalanadi)  *  /  public  static  class
Edge (public final String v1, v2; public final int dist; public Edge (String v1, String
v2,   int   dist)   (this.v1   \u003d   v1;   this.v2   \u003d   v2;   this.dist   \u003d   dist;))   /   **
Grafikning bitta tepasi,  qo'shni  tepaliklarni  xaritalash bilan to'ldirilgan * /  jamoat
statik klassi Vertex taqqoslashni amalga oshiradi   (public final String name; public
int   dist   \u003d   Integer.MAX_VALUE;   //   MAX_VALUE   cheksiz   deb   taxmin
qilingan   public   Vertex   previous   \u003d   null;   public   final   Map   qo'shnilar   \u003d
yangi HashMap<>(); public Vertex (string nomi) (this.name \u003d name;) private
void   printPath   ()   (if   (this   \u003d\u003d   this.previous)   (System.out.printf   ("%   s",
this.name);)   else   if   (   this.previous   \u003d\u003d   null)   (System.out.printf   ("%   s
(unreaching)",   this.name);)   else   (this.previous.printPath   ();   System.out.printf   ("-\
u003e%   s   (   %   d)   ",   this.name,   this.dist);))   public   int   ComparTo   (Vertex   other)
(return   Integer.compare   (dist,   other.dist);))   /   **   qirralarning   to'plamidan   grafik
tuzadi   *   /   umumiy   grafik   (qirralarning   qirralari)   (grafik   \u003d   yangi
HashMap<>(qirralarning uzunligi); // (Edge e: qirralari) uchun barcha tepaliklarni
topish uchun bitta o'tish (agar (! graph.containsKey (e.v1)) graph.put (e.v1, yangi
Vertex (e.v1));   agar   (!   grafasi).  containsKey  (e.v2))  graph.put   (e.v2,  yangi  vertex
(e.v2));)   //   (Edge   e:   qirralari)   uchun   qo'shni   tepaliklarni   o'rnatish   uchun   yana   bir o'tish   (graph.get   (e.v1).   qo'shnilar.put   (graph.get   (e.v2),   e.dist);
//graph.get(e.v2).neighbors.put(graph.get(e.v1),   e.dist);   //   also   buni
yo'naltirilmagan   grafik   uchun   bajaring))   /   **   Belgilangan   vertex   *   /   public   void
dijkstra   (String   startName)   (agar   (!   graph.containsKey   (startName)))
(System.err.printf  ("Graph   doesn"  t  start  vertex  o'z   ichiga  oladi   \\   "%  s   \\"  \\   n  ",
startName);   return;)   final   vertex   source   \u003d   graph.get   (startName);
NavigableSet   q   \u003d   yangi   TreeSet<>();   //   (Vertex   v:   graph.values   \u200b\
u200b()) (v.previous \u003d v \u003d\u003d manba? manba: null; v.dist \u003d v \
u003d\u003d manba? 0: Integer.MAX_VALUE; q. qo'shish (v);) dijkstra (q); ) / **
Ikkilik   uyum   yordamida   dijkstra   algoritmini   amalga   oshirish.   *   /   Private   void
dijkstra   (final   NavigableSet   q)   (Vertex   u,   v;   while   (!   q.isEmpty   ())   (u   \u003d
q.pollFirst   ();   //   eng   qisqa   masofaga   ega   bo'lgan   vertex   (birinchi   takrorlash
manbani qaytaradi), agar (u.dist \u003d\u003d Integer.MAX_VALUE)) break; // u
(va   boshqa   har   qanday   tepaliklarni)   e'tiborsiz   qoldirishimiz   mumkin,   chunki   ular
ulanib   bo'lmaydigan   //   har   bir   qo'shniga   masofani   ko'rib   chiqing   (Map.Entry   a:
u.neighbors.entrySet ()) (v \u003d a.getKey (); // bu iteratsiyadagi qo'shni final int
alternateDist   \u003d   u.dist   +   a.getValue   ();   if   (alternateDist<   v.dist)   {   //   shorter
path   to   neighbour   found   q.remove(v);   v.dist   =   alternateDist;   v.previous   =   u;
q.add(v); } } } } /** Prints a path from the source to the specified vertex */ public
void   printPath(String   endName)   {   if   (!graph.containsKey(endName))
{   System.err.printf("Graph   doesn"t   contain   end   vertex   \"%s\"\n",   endName);
return;   }   graph.get(endName).printPath();   System.out.println();   }   /**   Prints   the
path from the source to every vertex (output order is not guaranteed) */ public void
printAllPaths()   {   for   (Vertex   v:   graph.values())   {   v.printPath();
System.out.println(); } } }
</i+1<<"></i+1<<">
C
# shu jumladan   # shu jumladan   # shu jumladan   // # BIG_EXAMPLE typedef
struct   node_t   node_t,   *   heap_t   ni   belgilang;   typedef   struct   edge_t   edge_t;   struct
edge_t (node_t * nd; / * ushbu chekkaning maqsadi * / edge_t * birodar; / * yakka
bog'langan ro'yxat uchun * / int len; / * chekka xarajatlar * /); struct node_t (edge_t
* edge; / * qirralarning alohida bog'langan ro'yxati * / node_t * orqali; / * bu erda
oldingi tugun eng qisqa yo'lda * / double dist; / * origining tugunidan masofa * /
char nomi; / * the, er , name * / int heap_idx; / * masofani yangilash uchun uyum
holatiga havola * /); / * --- qirralarni boshqarish --- * / #ifdef BIG_EXAMPLE #
BLOCK_SIZE-ni aniqlang (1024 * 32 - 1) #else # define BLOCK_SIZE 15 #endif
edge_t   *   edge_root   \u003d   0,   *   e_next   \u003d   0;   /   *   Xotirani   boshqarish   haqida
o'ylamang,   ular   nuqta   yonida.   E_next   \u003d   malloc   (sizeof   (edge_t))   *   /   void
add_edge (node_t * a, node_t * b, double d) (if (e_next \u003d\u003d edge_root) )
(edge_root   \u003d   malloc   (sizeof   (edge_t)   *   (BLOCK_SIZE   +   1));
edge_root.sibling   \u003d   e_next;   e_next   \u003d   edge_root   +   BLOCK_SIZE;)   -
e_next;   e_next-\u003e   nd   \u003d   b;   e_next-\u003e   len   \u003d   d;   e_next   -\u003e aka-uka   \u003d   \u200b\u200ba-\u003e   chekka;   a-\u003e   chekka   \u003d   e_next;)
bo'sh bo'shliqlar () (uchun (; edge_root; edge_root \u003d e_next) (e_next \u003d
edge_root.sibling;   erkin   (edge_root);))   /   *   ---   ustuvor   navbatdagi   narsalar   ---   *   /
heap_t * heap; int heap_len; void set_dist (node_t * nd, node_t * via, double d) (int
i, j; / * allaqachon yaxshi yo'lni bilar * / if (nd-\u003e via && d\u003e \u003d nd-\
u003e   dist)   return;   /   *   mavjud   uyum   yozuvini   toping   yoki   yangisini   yarating   *   /
nd-\u003e   dist   \u003d   d;   nd-\u003e   orqali   \u003d   orqali;   i   \u003d   nd-\u003e
heap_idx; agar (! i) i \u003d ++ heap_len; / * upheap * / for (; i\u003e 1 && nd-\
u003e  dist<  heap->dist;  i  \u003d  j)   (heap   [i]   \u003d  heap  [j])   -\u003e  heap_idx  \
u003d i; heap [i] \u003d nd; nd-\u003e heap_idx \u003d i; ) node_t * pop_queue ()
(node_t * nd, * tmp; int i, j; agar (! heap_len) 0 qaytarsa; / * etakchi elementni olib
tashlang,  quyruq elementini   o'sha  joyga  torting va  pastga  tushiring  * /   nd \u003d
heap; tmp \u003d heap; for (i \u003d 1; i< heap_len && (j = i * 2) <= heap_len; i =
j) { if (j < heap_len && heap[j]->dist\u003e heap-\u003e dist) j ++; if (heap [j] -\
u003e dist\u003e \u003d tmp-\u003e dist) break; (heap [i] \u003d heap [j]) -\u003e
heap_idx \u003d i; ) heap [i] \u003d tmp; tmp-\u003e heap_idx \u003d i; return nd;
)   /   *   ---   Dijkstra   materiallari;   erishib   bo'lmaydigan   tugunlar   hech   qachon
qilmaydi   ichiga   navbat --- * / void calc_all (node_t * start) (node_t * lead; edge_t *
e; set_dist (start, start, 0); while ((lead \u003d pop_queue ())) for (e \u003d lead-\
u003e   edge;   e;   e   \u003d   e-\u003e   aka-uka)   set_dist   (e-\u003e   nd,   qo'rg'oshin,
qo'rg'oshin-\u003e dist + e-\u003e len);) bo'sh show_path (node_t * nd) (agar (nd-\
u003e   orqali   \u003d\u003d   nd)   printf   (   "%   s",   nd-\u003e   name);   else   if   (!   nd-\
u003e   via)   printf   ("%   s   (unracaching)",   nd-\u003e   name);   else   (show_path   (nd-\
u003e via);   printf  ("-)  \u003e%   s  (%  g)  ",  nd-\u003e name,  nd-\u003e  dist);))   int
main   (void)   (#ifndef   BIG_EXAMPLE   int   i;   #   define   N_NODES   ("   f   "-"   a   "+   1)
node_t * tugunlar \u003d calloc (sizeof (node_t), N_NODES); uchun (i \u003d 0;
i<   N_NODES;   i++)   sprintf(nodes[i].name,   "%c",   "a"   +   i);   #   define   E(a,   b,   c)
add_edge(nodes   +   (a   -   "a"),   nodes   +   (b   -   "a"),   c)   E("a",   "b",   7);   E("a",   "c",   9);
E("a", "f", 14); E("b", "c", 10);E("b", "d", 15);E("c", "d", 11); E("c", "f", 2); E("d",
"e",  6);   E("e",  "f", 9);  #  undef  E  #else  /*  BIG_EXAMPLE  */   int  i, j,  c;  #  define
N_NODES 4000 node_t *nodes = calloc(sizeof(node_t), N_NODES); for (i = 0; i
< N_NODES; i++) sprintf(nodes[i].name, "%d", i + 1); /* given any pair of nodes,
there"s   about   50%   chance   they   are   not   connected;   if   connected,   the   cost   is
randomly chosen between 0 and 49 (inclusive! see output for consequences) */ for
(i   =   0;   i   <   N_NODES;   i++)   {   for   (j   =   0;   j   <   N_NODES;   j++)   {   /*   majority   of
runtime is actually spent here */ if (i == j) continue; c = rand() % 100; if (c < 50)
continue;   add_edge(nodes   +   i,   nodes   +   j,   c   -   50);   }   }   #endif   heap   =
calloc(sizeof(heap_t), N_NODES + 1); heap_len = 0; calc_all(nodes); for (i = 0; i
<   N_NODES;   i++)   {   show_path(nodes   +   i);   putchar("\n");   }   #if   0   /*   real
programmers   don"t   free   memories   (they   use   Fortran)   */   free_edges();   free(heap);
free(nodes); #endif return 0; }
PHP $   edge,   "cost"   \u003d\u003e   $   edge);   $   qo'shnilar   [$   edge]   \u003d   array
("end"   \u003d\u003e   $   edge,   "cost"   \u003d\u003e   $   edge);   )   $   vertices   \u003d
array_unique ($ vertices); foreach ($ vertices $ vertex sifatida) ($ dist [$ vertex] \
u003d INF; $ oldingi [$ vertex] \u003d NULL;) $ dist [$ source] \u003d 0; $ Q \
u003d $ tepaliklar; while (count ($ Q)\u003e 0) (// TODO - Minimal $ min \u003d
INF   olishning   tezroq   usulini   toping;   foreach   ($   Q   $   $   vertex))   (if   ($   dist   [$
vertex])<   $min)   {   $min   =   $dist[$vertex];   $u   =   $vertex;   }   }   $Q   =   array_diff($Q,
array($u));   if   ($dist[$u]   ==   INF   or   $u   ==   $target)   {   break;   }   if
(isset($neighbours[$u]))   {   foreach   ($neighbours[$u]   as   $arr)   {   $alt   =   $dist[$u]   +
$arr["cost"];   if   ($alt   <   $dist[$arr["end"]])   {   $dist[$arr["end"]]   =   $alt;
$previous[$arr["end"]]   =   $u;   }   }   }   }   $path   =   array();   $u   =   $target;   while
(isset($previous[$u]))   {   array_unshift($path,   $u);   $u   =   $previous[$u];   }
array_unshift($path,   $u);   return   $path;   }   $graph_array   =   array(array("a",   "b",   7),
array("a",   "c",   9),   array("a",   "f",   14),   array("b",   "c",   10),   array("b",   "d",   15),
array("c", "d", 11), array("c", "f", 2), array("d", "e", 6), array("e", "f", 9)); $path =
dijkstra($graph_array, "a", "e"); echo "path is: ".implode(", ", $path)."\n";
Xulosa
      Xulosa   qilib   aytganda   Algoritm   bilan   ishlash   barcha   turdagi   dasturlash
tillarida   ishlash   uchun   kerak   buladi.   Algoritmsiz   biror   bir   dasturlash   tilida   dastur
yaratib bulmaydi. Xar  bir  dasturning dastlab  algoritmini yaratib olish zarur. Agar
biz   dasturimizning   ketma-ketligini   bilmasak   ,   u   dastur   biz   uylagandan   kuproq
xajmni   egallashi   mumkin   ekan.   Men   C++   dasturlash   tilida   malumotlarni   izlash   ,
saralash, qayta ishlash kabi amallarni yuqorida kursatib utilganidagidek bir va ikki
ulchovli   massivlarda   bajarilganini   kurib   bilim   va   kunikmalarga   ega   buldim.   Men
C++   dasturi   strukturasi   xaqida,   belgilar   bayoni,   algoritm   va   dastur   tushunchasi ,
malumotlarni   kiritish   va   chiqarish   operatorlari   xamda   dasturda   ishlatiladigan
toifalar,   ifodalar   va   kunikmalarga   ega   buldim.   Algoritmlash   va   dasturlash   tillari
buyicha   yozilgan   bir   nechta   kitoblar   bilan   tanishib   chiqdim   va   ulardan   uzimga
kerakli   malumotlarni   oldim.   Kurs   ishimda   Deyskra   algoritmining   ishlash
prinsplarini ko’rib uning ishlashini dasturlarda amaliy ko’rib chiqdim.    
Foydalangan adabiyotlar:
1.   В.А.Успенский,     А.Л.Семенов.     Теория     алгоритмов:     основные     открытия    
и    
приложения.   –   М:   Наука,   1987,   287   с.    
2.     Т..Кормен,     Ч.Лейзерсон,     Р.Ривест.     Алгоритмы:     построение     и     анализ   Се
р:Классические   учебники.   М.:   МЦНМО,   2001.-   960   с.     3.     Тыугу   Х.   Концептуальное   программирование.   М:   Наука,   1984.    
4.       Н.   Вирт.   Алгоритмы   и   структуры   данных.   –   Досса,   Хамарайан,   1997.    
5.      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 .
6.   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 .
7.   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 .
8.   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 .
9. 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.
10.   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 .
11. 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 .
12.   Raman,   Rajeev   (1997).   "Recent   results   on   the   single-source   shortest   paths
problem".   SIGACT News.   28   (2): 81–87.   doi : 10.1145/261342.261352 . 13.     Thorup,   Mikkel   (2000).   "On   RAM   priority   Queues".   SIAM   Journal   on
Computing.   30   (1): 86–109.   doi : 10.1137/S0097539795288246 .
14.  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 .
</c<<"\t\t"<<dist[i]<

Mavzu: Eng qisqa masofani toppish. Deykstra algoritmi va uni tahlil qilish. Reja: 1 . Kirish . 2. Asosiy qisim 1. Eng qisqa yo’llar masalalarining turlari. 2. Deykstra algoritmning so’zli tavsifi 3. Masalaning qo’yilishi. 4. Deysktra algoritmi. 3 . Xulosa. 4. Foydalanilgan 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. 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. Oxir-oqibat, bu algoritm mening shon-shuhratimning asosiy toshlaridan biri bo'lgan. - Edzger Dijkstra, ACM bilan aloqa, Philip L. Frana, 2001. 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. 1. 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 irralar 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 , turdagi har bir uchlar juftliklari orasida va boshqalar. 2. Deykstra algoritmning so’zli tavsifi Eng qisqa masofani topish masalalarni yechish uchun Deykstra algoritmi ancha qulay va yahshi deb topilgan. Algoritm quyidagi qa damlardan iborat: 1. Dastlab, berilgan (Lex) uchidan qolgan barcha uchlargacha bir qirra uzunligidagi masofalar aniqlanadi. 2. Ulardan eng qisqasi “doimiy eng qisqa masofa” sifatida belgilanadi (Lex va BVa uchlari qirrasi). 3. Aniqlangan masofa BVa dan boshqa bor uchlargacha masofalarga qo’shiladi. 4. Hosil bo’lgan yig’indilar dastlab aniqlangan Lex dan qolgan uchlargacha bo’lgan masofalar bilan taqqoslanadi. Natijada masofasi qisqaroq bo’lgan uchning qirrasi tanlanadi. 5. BVa uchi, eng qisqa masofa aniqlangan uch sifatida, ruyhatdan o’chiriladi.

Ruyhatga boshqa uch qo’yiladi, masalan, Roa. Bva o’z navbatida, boshqa, izlanayotgan ruyhatga qo’yiladi. Keyingi eng qisqa masofani topish uchun butun jarayon qayta bajariladi. BVa dan keyin yana bir uch ruyhatga qo’yiladi. Dastlabkisi esa ruyhatdan o’chiriladi. Sikl Bed va Lex uchlarini bog’lash uchun belgilangan qirralar aniqlanishi bilan to’xtatiladi. 3. Deyskra Algoritmi. Grafdagi eng qisqa marshrutlar uchun ko'plab qidiruv algoritmlari bo'yicha, Habreda faqatgina Floyd-Worschall algoritmining ta'rifi topildi. Ushbu algoritm grafikaning 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 grafikning boshqa vertikalari orasida topadi. Ushbu algoritmning nochorligi, agar grafika salbiy og'irliklarga ega bo'lsa, u noto'g'ri ishlaydi. Misol uchun, G quyidagi ko'rsatgichni bajaring: tasvirUshbu grafikani matritsa sifatida taqdim etamiz:tasvir Keling, vertex 1ni manba sifatida qabul qilaylik, shuning uchun vertex 1dan eng kichkina marshrutlarni 2, 3, 4 va 5-ustungacha topamiz.Ushbu algoritm grafaning barcha verticesida yineleyadi va manba verteksidan muayyan vertexga ma'lum minimal masofa bo'lgan belgilarga ularni belgilaydi. Masalan, ushbu algoritmni ko'rib chiqaylik.Keling, 1 tepalikka tegni 0 ga teng qilamiz, chunki bu vertex manba hisoblanadi. Qolgan tepaliklar abadiylikka teng teglar bilan belgilanadi. Keyinchalik, minimal yorlig'i (hozirda vertex 1) bo'lgan vertikal W ni tanlang va vertex W dan mediatorlar vertikalarini o'z ichiga olmaydi. W belgisining yig'indisiga teng bo'lgan belgini va hisobga olingan vertikalarning har biriga qarab, Vdan vertikaga yo'llarni belgilang, lekin natijada faqat oldingi qiymatdan kamroq bo'lsa. Agar bu miqdor kam bo'lmasa, oldingi belgini o'zgartirmang.Biz W dan to'g'ridan-to'g'ri yo'lni egallagan barcha vertikalarni ko'rib chiqdik, keyin V ga tashrif buyurib, tepaligini eng past qiymatga ega bo'lganlardan tanlaymiz va u keyingi V tepasida bo'ladi. Bu holda, bu birinchi 2 yoki 5. Agar bir xil teglar bilan bir necha vertikalar mavjud bo'lsa, ularning qaysi biri W ni tanlashimiz muhim emas. Biz vertex 2 ni tanlaymiz. Biroq, undan bitta chiqish yo'li yo'q, shuning uchun darhol ushbu vertexni tashrif buyurgan deb belgilab olamiz va keyingi vertikaga minimal belgisi bilan kiramiz. Bu safar faqat vertex 5da eng kam belgilar mavjud. 5-dan 5-gacha to'g'ridan-to'g'ri yo'llar mavjud bo'lgan barcha vertikalarni ko'rib

chiqing, ammo hozircha ular tashrif buyurilgan deb bo'lmaydi. Shunga qaramay , vertex W yorlig'ining yig'indisi va W dan joriy vertexning chekkasini topamiz va agar bu summa oldingi yorliqdan kamroq bo'lsa, biz natijada olingan qiymat bilan etiketaning qiymatini o'zgartiramiz. Rasmga asoslanib, biz uchinchi va to'rtinchi zirvalarning yorliqlari kichikroq ekanligini, ya'ni manba tepasidagi bu tepaliklarga nisbatan qisqaroq yo'lni topdik. Keyinchalik, 5 vertexni tashrif buyurgan deb belgilang va eng past belgisi bo'lgan keyingi vertikani tanlang. Yuqorida keltirilgan barcha harakatlar takrorlanmagan vertikalar mavjud ekan, takrorlang. Barcha amallarni bajarib bo'lgach, biz quyidagi natijani qo'lga kiritamiz: Dijkstra algoritmi Grafikdagi 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 grafika 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 grafikalar 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 grafikalar 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