DSA eng qisqa yo‘l
Eng qisqa yo‘l masalasi
Eng qisqa yo‘l masalasi informatika sohasida mashhur.
Eng qisqa yo‘l masalasini yechish — grafdagi ikki cho‘qqi (yoki tugun) orasidagi mumkin bo‘lgan eng qisqa marshrut yoki yo‘lni topish demakdir.
Eng qisqa yo‘l masalasida graf yo‘l tarmog‘idan tortib aloqa tarmog‘igacha har qanday narsani ifodalashi mumkin, bunda cho‘qqilar chorrahalar, shaharlar yoki routerlar, qirralar esa yo‘llar, parvoz yo‘nalishlari yoki ma’lumot uzatish kanallari bo‘lishi mumkin.
Yuqoridagi grafda D cho‘qqisidan F cho‘qqisigacha eng qisqa yo‘l D->E->C->F bo‘lib, yo‘lning umumiy vazni 2+4+4=10 ga teng. D’dan F’ga boshqa yo‘llar ham mavjud, ammo ularning umumiy vazni kattaroq, shuning uchun ularni eng qisqa yo‘l deb hisoblab bo‘lmaydi.
Eng qisqa yo‘l masalasining yechimlari
Dijkstra algoritmi va Bellman-Ford algoritmi bitta boshlang‘ich cho‘qqidan boshqa barcha cho‘qqilargacha bo‘lgan eng qisqa yo‘lni topadi.
Eng qisqa yo‘l masalasini yechish — qirralar bo‘ylab mumkin bo‘lgan eng kichik umumiy vazn bilan bir cho‘qqidan boshqasiga o‘tish mumkin bo‘lgan yo‘lni topmagunimizcha grafdagi qirralarni tekshirish demakdir.
Yo‘lni tashkil etuvchi qirralar bo‘ylab vaznlarning bu yig‘indisi yo‘l narxi (path cost) yoki yo‘l vazni (path weight) deb ataladi.
Dijkstra algoritmi yoki Bellman-Ford algoritmi kabi eng qisqa yo‘llarni topuvchi algoritmlar bitta boshlang‘ich cho‘qqidan boshqa barcha cho‘qqilargacha bo‘lgan eng qisqa yo‘llarni topadi.
Boshlanishiga algoritmlar boshlang‘ich cho‘qqidan barcha cho‘qqilargacha bo‘lgan masofani cheksiz uzun deb belgilaydi. Algoritmlar ishlashi davomida cho‘qqilar orasidagi qirralar qayta-qayta tekshiriladi va oxir-oqibat eng qisqa yo‘llar topilgunga qadar qisqaroq yo‘llar ko‘p marta topilishi mumkin.
Har safar qirra tekshirilib, bu cho‘qqigacha qisqaroq masofa topilishi va yangilanishiga olib kelsa, bu relaksatsiya (relaxation) yoki qirrani relaksatsiya qilish (relaxing) deb ataladi.
Musbat va manfiy qirra vaznlari
Dijkstra algoritmi kabi eng qisqa yo‘llarni topuvchi ba’zi algoritmlar faqat barcha qirralari musbat bo‘lgan graflarda eng qisqa yo‘llarni topa oladi. Musbat masofali bunday graflarni tushunish ham eng oson, chunki cho‘qqilar orasidagi qirralarni joylar orasidagi masofalar deb tasavvur qilishimiz mumkin.
Agar qirra vaznlarini bir cho‘qqidan boshqasiga o‘tishda yo‘qotiladigan pul deb talqin qilsak, yuqoridagi grafdagi A cho‘qqisidan C cho‘qqisiga boruvchi 4 ga teng musbat qirra vazni A’dan C’ga borish uchun $4 sarflashimiz kerakligini anglatadi.
Ammo graflarda manfiy qirralar ham bo‘lishi mumkin va bunday graflarda eng qisqa yo‘llarni topish uchun Bellman-Ford algoritmidan foydalanish mumkin.
Xuddi shunday, agar qirra vaznlari yo‘qotilgan pulni ifodalasa, yuqoridagi grafdagi C cho‘qqisidan A’ga yo‘nalgan -3 manfiy qirra vaznini C’dan A’ga borishda yo‘qotiladigan puldan ko‘ra ko‘proq pul ishlab topiladigan qirra deb tushunish mumkin. Masalan, C’dan A’ga borishda yoqilg‘i narxi $5 bo‘lsa va C’dan posilkalarni olib, A’ga yetkazib berganimiz uchun bizga $8 to‘lansa, yo‘qotilgan pul -3 bo‘ladi, ya’ni aslida jami $3 ishlab topamiz.
Eng qisqa yo‘l masalalarida manfiy sikllar
Agar grafda manfiy sikllar bo‘lsa, eng qisqa yo‘llarni topish imkonsiz bo‘lib qoladi.
Manfiy sikl mavjudligi shuni anglatadiki, grafda aylana bo‘ylab qayta-qayta yurish mumkin bo‘lgan yo‘l bor va shu aylanani tashkil etuvchi qirralarning umumiy yo‘l vazni manfiy.
Quyidagi grafda A->E->B->C->A yo‘li manfiy sikl hisoblanadi, chunki umumiy yo‘l vazni 5+2-4-4=-1 ga teng.
Manfiy sikllari bor grafda eng qisqa yo‘llarni topib bo‘lmasligining sababi shundaki, algoritmni ishlatishda davom etib, har doim bundan ham qisqaroq yo‘llarni topish mumkin bo‘ladi.
Masalan, yuqoridagi grafda D cho‘qqisidan boshqa barcha cho‘qqilargacha bo‘lgan eng qisqa masofani qidirayapmiz, deylik. Dastlab faqat D->E qirrasi bo‘ylab yurib, D’dan E’gacha masofa 3 ekanini topamiz. Ammo shundan so‘ng E->B->C->A->E manfiy sikli bo‘ylab bir marta aylanib chiqsak, E’gacha masofa 2 ga aylanadi. Yana bir marta aylanib chiqqach, masofa 1 bo‘ladi — bu yanada qisqaroq, va hokazo. Manfiy sikl bo‘ylab har doim yana bir marta aylanib, E’gacha qisqaroq masofani topishimiz mumkin, demak eng qisqa masofani hech qachon topib bo‘lmaydi.
Yaxshiyamki, manfiy qirrali graflarda ishlaydigan Bellman-Ford algoritmini manfiy sikllarni aniqlash imkoniyati bilan amalga oshirish mumkin.
W3Schools Pathfinder
Yutuqlaringizni kuzating – bu bepul!