Deykstra Algoritmi


Mavzu: Deykstra Algoritmi. MUNDARIJA KIRISH ....................................................................................................................................................................................... 1.Graflar nazariyasining asosiy tushunchalari .......................................................................................................................... 2.Deykstra algoritmining paydo bo’lishi ................................................................................................................................... 3.Deykstra Algoritmi ................................................................................................................................................................ 4. Eng qisqa yo’llar masalalarining turlari .............................................................................................................................. 5.Deykstra algoritmning so’zli tavsifi ...................................................................................................................................... 6.Deykstra algoritmning C++ da kodi ..................................................................................................................................... 7.Tegishli muammolar va algoritmlar ..................................................................................................................................... Xulosa .................................................................................................................................................................................... Foydalangan adabiyotlar: .......................................................................................................................................................
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