Biz o’tgan mavzularda ko’rib o’tganimiz, minimum spanning tree – edge’lari weight’ga ega undirected graph‘dagi barcha vertex’larni o’z ichiga olgan qisqa yo’lni topishga bag’ishlangan edi. Edge-weight’li directed graph uchun esa shortest path (qisqa yo’l) algoritmlari bilan tanishib chiqamiz.
Shortest path – directed graph’da bir vertex’dan boshqa vertex’ga eng qisqa yo’lni topishni nazarda tutadi. Bunda, yo’lning qisqaligi edge weight’larining yig’indisiga bog’liq. Masalan quyidagi graph’da 0 vertex’dan 6 ga qisqa yo’lni topish kerak bo’lsin.
Qisqa yo’l 0 -> 2 -> 7 -> 3 -> 6 ga teng. Vaholanki, 0 dan 6 gacha boshqa uzunroq yo’llar ham mavjud: 0 -> 4 -> 7 -> 3 -> 6, 0 -> 4 -> 5 -> 1 -> 3 -> 6
Shortest path’ni topish masalasi uzoq yillar davomida odamlarni qiziqtirib kelgan. Masalan qisqa masofa/vaqt’da shaharlarni aylanib chiqish, suv quvurlari o’tkazish, traffikni rejalashtirish va h.k. Hozirgi kunga kelib, shortest path algoritmlari asosida GPS-navigatsiya, kartalar bizga optimal yo’lni topib beradi.
Shortest paths masalasining turli xil variantlari mavjud.
- Source-sink. Odatiy bir vertex’dan boshqa vertex’ga qisqa yo’lni topish.
- Single source. Bir vertex’dan qolgan barcha vertex’larga qisqa yo’llarni topish.
- All pairs. Barcha bog’langan vertex’lar orasidagi qisqa yo’llarni topish
Shortest path hususiyatlari
Algoritmlarni boshlashdan oldin ba’zi muhim jihatlarni aniqlashtirib olish zarar qilmaydi.
Path’lar directed bo’ladi. Shortest path faqat edge’larning yo’nalishini bo’yicha topiladi.
Weight’lar masofani belgilamaydi. Weight’lar masofaga bog’liq ham bo’ladi, to’g’ri. Ammo aslida weight – edge’ning ustunligini (afzalligini) aniqlovchi o’lchov. Batafsil – bu yerda.
Barcha vertex’larga kirib chiqish shartmas. Umuman, barcha vertex’larga ham path bo’lmasligi mumkin. Agar ikki vertex’ning orasidagi path’ni topish kerak bo’lsayu, vertex’lar orasida path umuman bo’lmasa, demak shortest path yo’q deb hisoblanadi.
Negativ (weight < 0) weight’lar ishni qiyinlashtiradi. Hozircha biz positiv (weight > 0) weight’larni ko’rib chiqamiz. Negativ weight’lar haqida alohida mavzu bo’ladi (Insha Alloh).
Shortest path’lar odatda oson bo’ladi. Bizning algoritmlar 0 weight’li sikl hosil qiluvchi edge’larni tushirib qoldiradi, shuning uchun 0 weight edge aralashgan path cycle hosil qilsa ham, algoritm cycle yo’q deb hisoblaydi.
Shortest path’lar unikal bo’lmasligi ham mumkin. Agar graph’da bir xil path’lar topiladigan bo’lsa, biz ulardan birini olamiz.
Parallel va ichki sikl (self-loop) edgelar uchrashi mumkin. Ular algoritmning ishiga ta’sir qilmaydi.