Mustaqil ish mavzu: Marshurutlar va ularning vazifalari Qabullagan: Bajargan: nukus-2024

G  (V ,U )
oriyentirlangan graf berilgan bo‘lsin, bu yerda
V  {1,2,..., m}

. G grafning biror
s V
uchidan boshqa
t V
uchiga boruvchi yo‘llar

orasida uzunligi eng kichik bo‘lganini topish masalasi bilan shugʻullanamiz. Bu masalani minimal uzunlikka ega yo‘l haqidagi masala deb ataymiz. Quyida bu masalaning umumlashmasi hisoblangan masalani qarab, uni ham o‘sha nom bilan ataymiz.

Grafdagi
(i, j)
yoyning uzunligini
^cij
bilan belgilab,


C  (c_ij ), i, j  1, m ,

matritsa berilgan deb hisoblaymiz. Yuqorida ta’kidlaganlarimizga ko‘ra,

C matritsaning
^cij
elementlari orasida manfiylari yoki nolga tenglari ham

bo‘lishlari mumkin. Agar grafda biror i uchdan chiqib j uchga kirruvchi yoy mavjud bo‘lmasa, u holda bu yoyning uzunligini cheksiz katta deb qabul qilamiz ( c_ij   ). Bundan tashqari, G grafda umumiy uzunligi

manfiy bo‘lgan sikl mavjud emas deb hisoblaymiz, chunki aks holda uzunligi eng kichik bo‘lgan yo‘l mavjud emas⁵.

Minimal uzunlikka ega yo‘l haqidagi masalani hal etish usullari orasida Deykstra⁶ tomonidan taklif etilgan algoritm ko‘p qo‘llaniladi. Quyida grafning 1 belgili uchidan chiqib (bu uchni manba deb qabul ^{qilamiz) grafdagi ixtiyoriy} k ^{uchgacha (bu uchni oxirgi uch deb} hisoblaymiz) eng qisqa uzunlikka ega yo‘lni topish imkonini beruvchi Deykstra algoritmi keltirilgan.