Nazorat savollari: Algoritm nima?

(Shuningdek o'qing: Diskret matematikaning 7 asosiy bo'limi)


Dijkstra algoritmi - bu bizga ma'lum bir boshlang'ich tugundan grafaning barcha boshqa tugunlariga eng qisqa yo'lni taqdim etish uchun takrorlanadigan algoritmik jarayon. Minimal uzunlikdagi daraxtdan farq qiladi, chunki ikkita tepalik orasidagi eng qisqa masofa grafikaning barcha tepalarini o'z ichiga olmaydi.


Shuni ta'kidlash kerakki, Dijkstra algoritmi faqat barcha og'irliklar ijobiy bo'lganda qo'llaniladi, chunki bajarish paytida qirralarning og'irliklari eng qisqa yo'lni topish uchun qo'shiladi.


Va shuning uchun agar biron bir og'irlik grafikaning chekkalarida salbiy bo'lsa, algoritm hech qachon to'g'ri ishlamaydi. Biroq, bunday hollarda Bellman-Ford algoritmi kabi ba'zi algoritmlardan foydalanish mumkin.


Bundan tashqari, kenglik bo'yicha birinchi qidiruv (BFS) o'lchovsiz grafika uchun eng qisqa yo'lni hisoblash uchun yoki uning chekkalarida bir xil narxga ega bo'lgan vaznli grafika uchun ishlatilishi mumkinligi ham ma'lum.


Ammo agar tortilgan grafikada cheklovlar teng bo'lmagan xarajatlarga ega bo'lsa, unda BFS bir xil narxlardagi qidiruvni amalga oshiradi. Endi nima?


Tugunlarni ildizdan chuqurligi bo'yicha uzaytirish o'rniga, bir xil narxlardagi qidirish tugunlarni ildizidan kelib chiqadigan xarajatlar tartibida rivojlantiradi. Va bu algoritmning bir varianti Dijkstra algoritmi sifatida qabul qilinadi.


Odatda, Dijkstra algoritmi yengillik printsipi bo'yicha ishlaydi, bu erda aniq masofani yaqinlashishi eng qisqa masofaga erishilguncha ko'proq mos keladigan qiymatlar bilan barqaror ravishda siljiydi.


Bundan tashqari, har bir tugunga taxminiy masofa har doim haqiqiy masofani ortiqcha baholaydi va odatda avvalgi qiymatining eng kichigi bilan yaqinda aniqlangan yo'lning masofasi bilan almashtiriladi.