logo
  1. Главная страница
  2. Дипломные работы
  3. Общий
  4. Deykstra Algoritmi

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

Похожие

Eng qisqa masofani toppish. Deykstra algoritmi va uni tahlil qilish.
KRASKAL ALGORITMI
Timsort saralash algoritmi
Shiber-vishkin algoritmi
Xon saralash algoritmi