Deykstra algoritmi tahlili. Graflarda eng qisqa masofani aniqlash Mualliflar: Asqarov Qudrat

Deykstra algoritmi tahlili. Graflarda eng qisqa masofani aniqlash
Mualliflar:
Asqarov Qudrat - Qoraqalpoq davlat universiteti stajyor o’qituvchisi
Annotatsiya
Ushbu maqolada graflarda eng qisqa masofani aniqlashda Deysktra algoritmidan foydalanish ko’rib chiqiladi. Deykstra algoritmiga ikki nuqta orasidagi eng qisqa yo'lni topish juda muhim bo'lgan ko'plab ilovalarda foydalaniladi. Masalan, u kompyuter tarmoqlari uchun marshrutlash protokollarida va xaritalar bilan ishlovchi tizimlar tomonidan boshlang'ich nuqta va chiquvchi nuqta o'rtasidagi eng qisqa yo'lni topish uchun ishlatiladi.
Kirish
Deykstra algoritmi graflarda manfiy bo'lmagan uch og'irligiga ega bo'lgan ko'plab bir manbali eng qisqa yo'l muammolarini hal qilish uchun mashhur algoritmdir, ya'ni grafdagi ikkita cho'qqi orasidagi eng qisqa masofani topishdir. U 1956 yilda gollandiyalik olim Edsger V. Deykstra tomonidan yaratilgan.
Algoritm tashrif buyurilgan cho'qqilar to'plamini va ko'rib chiqilmagan cho'qqilar to'plamini saqlaydi. U manba cho'qqisidan boshlanadi va iterativ ravishda manbadan eng kichik taxminiy masofaga ega bo'lmagan uchini tanlaydi. Keyin u ushbu cho'qqining qo'shnilariga tashrif buyuradi va agar qisqaroq yo'l topilsa, ularning taxminiy masofalarini yangilaydi. Bu jarayon maqsad cho'qqisiga yetguncha yoki barcha erishish mumkin bo'lgan cho'qqilarga tashrif buyurilgunga qadar davom etadi.
Deykstra algoritmini amalga oshirish uchun asosiy talablar

1. 
   Graf: Deykstra algoritmi har qanday grafda amalga oshirilishi mumkin, ammo u chekka og'irliklari manfiy bo'lmagan og'irlikdagi yo'naltirilgan graf bilan eng yaxshi ishlaydi va graf cho'qqilari va qirralarning to'plami sifatida ko'rsatilishi kerak.
   
2. 
   Source vertex: Deykstra algoritmi qidiruv uchun boshlang'ich nuqta bo'lgan manba tugunini talab qiladi.
   
3. 
   Belgilangan cho'qqi: Deykstra algoritmi ma'lum bir maqsad cho'qqisiga erishilgandan so'ng qidiruvni tugatish uchun o'zgartirilishi mumkin.
   
4. 
   Salbiy bo'lmagan qirralar: Deykstra algoritmi faqat ijobiy og'irliklarga ega bo'lgan graflarda ishlaydi, chunki jarayon davomida eng qisqa yo'lni topish uchun chekka og'irliklari qo'shilishi kerak. Grafda manfiy og'irlik bo'lsa, algoritm to'g'ri ishlamaydi. Tugun tashrif buyurilgan deb belgilangandan so'ng, ushbu tugunga boradigan joriy yo'l ushbu tugunga erishish uchun eng qisqa yo'l sifatida belgilanadi.