Њзбекистон республикаси олий ва њрта махсус

1
А 10 ^А2
₈ А₇

7
^{6 5} 9
А₃
10
8
^А8 ⁴

А 6
8
^А4 5
В
4
7
4
₃ ^А6 3 ₅
А₅ 5
А₉

5.2-rasm. A va V punktlarni o„zaro bog„lovchi temir yo„llar to„ri
Bu punktlar orasida temir yo„l bilan bog„langan juda ko„p punktlar mavjud bo„lishi mumkin. Bunda har qanday ikki punkt orasidagi masofa ma‟lum deb faraz qilamiz. Masalan, bu masofaning uzunligi 5.2-rasmdagi har ikki nuqtani

tutashtiruvchi kesma ustida yozilgan sonlardan iborat bo„lsin. A va B punktlarni eng qisqa yo„l bilan tutashtiruvchi yo„nalishni aniqlash masalasi qo„yiladi.
Masalani yechish uchun (1-1), (2-2), (3-3) chiziqlar yordamida berilgan temir yo„llar to„rini ayrim qismlarga (bosqichlarga) ajratamiz. (5.3-rasm).
(2-2) chiziqning transport yo„llari to„ri bilan kesishgan nuqtalarini D₁, D₂ , D₃

lar bilan, (3-3) chiziqning kesishgan nuqtalarini esa
C₁ ,C₂ ,C₃
nuqtalar bilan

belgilaymiz. Birinchi qadamda B nuqtadan qisqa masofani aniqlaymiz.
D₁ , D₂ , D₃
nuqtalargacha bo„lgan eng

B  D₁ : min(10, 8  4, 5  3  8)  10


B  bD₂ : min(10  8  5, 4  5, 5  3  5)  9 ,

B  bD₃ : min(5  2,5,
4  3  2,5)  7,5

А В
5.3-rasm. Ayrim qismlari ajratilgan A va V punktlarni o„zaro bog„lovchi temir yo„llar to„ri

5.3-rasmda
D₁ , D₂ , D₃
nuqtalardan so„nggi B punktgacha bo„lgan eng qisqa

masofa qavs ichida yozilgan. So„ngra (3-3) chiziqning transport yo„llari to„ri

kesishgan
C₁ ,C₂ ,C₃
nuqtalarni ko„ramiz. Bu nuqtalardan B nuqtagacha bo„lgan eng

qisqa masofani aniqlaymiz. Bu masofa

C₁ nuqta uchun
min(1 8 10, 1 7  4  2  9, 1 7  2  3  2  9, 1 7  2  2,5  7,5) 

 min(19,
23,
24,
20)  19 .

C₂ nuqta uchun
min(7  8 10, 9 10,
4  2  9,
2  3  2  9,
4  2,5  7,5) 

C₂ nuqta uchun
 min(25, 19, 15, 16, 14)  14 .

min(2  2,5  7,5, 2  3  2  9)  12 .

Bu masofalar shaklda qavs ichida yozilgan. 3-bosqichda A nuqtadan B

nuqtagacha bo„lgan eng qisqa masofa topiladi. Bu masofa quyidagicha aniqlanadi:
min(6  9 19, 6  5 14, 8  6 14, 8  3 12)  23.
So„ngra A nuqtadan eng qisqa masofa bo„ylab B nuqtaga boriladigan yo„lni belgilaymiz:
A  C₃  D₃  B .

6.