Asosiy k-qadam. Yetakchi satr va yetakchi ustun sifatida k satr va k ustunni
beramiz. Uchburchak operatorni D
k-1
matritsaning barcha d
ij
elementlariga qo‗llash
imkoniyatini ko‗rib chiqamiz. Agar d
ik
+ d
kj
< d
ij
, (i<>k, j<>k, i<>j) tengsizlik
bajarilsa, quyidagi amallarni bajaramiz:
−
D
k-1
matritsadagi d
ij
elementni d
ik
+ d
kj
yig‗indi bilan almashtirish
orqali D
k
matritsani hosil qilamiz;
−
S
k-1
matritsadagi s
ij
elementni k ga almashtirish orqali S
k
matrisani
hosil qilamiz.
k = k + 1 o‗rnatamiz va k qadamni takrorlaymiz.
8.3-rasmda tasvirlanganidek, D
k-1
matritsani taqdim qilish orqali
algoritmning k-nchi qadamida bajarilgan amallarni tushuntiramiz. Bu rasmda k satr
56
va k ustun yetakchi hisoblanadi. i satr 1 dan k - 1 gacha bo‗lgan istalgan satr, r satr
esa k + 1 dan n gacha bo‗lgan raqamli istalgan satr hisoblanadi. Xuddi shunday
tarzda ј ustun 1 dan k - 1 gacha bo‗lgan istalgan ustunni anglatadi, q ustun k + 1
dan n gacha bo‗lgan raqamli istalgan ustun hisoblanadi.
.
7.14- rasm. Floyd algoritmini tasvirlash
Uchburchak operatori quyidagicha amalga oshiriladi. Agar yetakchi satr va
ustun elementlarining yig‗indisi (kvadratlarda ko‗rsatilgan) qaralayotgan yetakchi
elementlarga mos keladigan ustun va satrning kesishmasida joylashgan
elementlardan (doiralarda ko‗rsatilgan) kichik bo‗lsa, u holda masofa (doiradagi
element) yetakchi elementlar orqali ko‗rsatilgan masofalar yig‗indisi bilan
almashtiriladi (8.3- rasm).
Algoritmning n qadamlari bajarilgandan keyin D
n
va S
n
matritsalar bo‗ycha i
va ј tugunlar orasidagi eng qisqa yo‗lni aniqlash quyidagi qoidalar bo‗yicha amalga
oshiriladi.
i va ј tugunlari orasidagi masofa D
n
matritsadagi d
ij
elementga teng.
i tugundan ј tugungacha bo‗lgan yo‗ldagi oraliq tugunlar S
n
matritsa
bo‗yicha aniqlanadi. s
ij
= k bo‗lsin, u holda i→ k → ј yo‗lga ega bo‗lamiz. Agar
satr
ustun
Yetakchi
ustun
ustun
Yetakchi
satr
satr
57
s
ik
= k va s
kj
= ј bo‗lsa, u holda barcha oraliq tugunlar topilganligi sababli, butun
yo‗l aniqlangan deb faraz qilamiz. Aks holda, ј tugundan k tugunga va k tugundan
ј tugungacha bo‗lgan yo‗llar uchun tavsiflangan protsedurani takrorlaymiz.
Misol. 8.4-rasmda tasvirlangan tarmoq uchun istalgan ikkita tugunlar
orasidagi eng qisqa yo‗llarni topamiz. Bu tarmoqning tugunlari orasidagi masofa
8.4-rasmda mos qirralarning yaqinidagi qo‗yilgan. (3, 5) qirra yo‗naltirilgan,
shuning uchun 5-nchi tugundan 3-nchi tugungacha harakatlanish mumkin emas.
Qolgan barcha qirralar har ikkala tomonlarga harakatlanishga ruxsat etadi (8.4-
rasm).
7.15- rasm. Floyd algoritmi uchun tarmoq tuzilishi
0-qadam. Dastlabki D
0
va S
0
matritsalar to‗g‗ridan-to‗g‗ri berilgan tarmoq
sxemasiga binoan quriladi. D
0
matritsa d
35
va d
53
elementlar juftligidan tashqari,
nosimmetrik hisoblanadi, bu yerda d
53
cheksizlikka teng, chunki 5-nchi tugundan
3-nchi tugunga o‗tish mumkin emas:
7.16-rasm. Berilgan tarmoq grafi uchun dastlabki holatlar matritsalari
1-qadam. D
0
matritsada yetakchi satr va ustun (k = 1) tanlangan. Juft ramka
bilan d
23
va d
32
elementlar ajratilgan, ular qiymatlarini uchburchak operator orqali
58
yaxshilash mumkin bo‗lgan D
0
matritsa elementlari orasida yagona elementlar
hisoblanadi. Shunday qilib, D
0
va S
0
matritsalar asosida D
1
va S
1
matritsalarni olish
uchun quyidagi amallarni bajaramiz.
d
23
ni d
21
+ d
13
= 3 + 10 = 13 bilan almashtiramiz va s
23
= 1 ni o‗rnatamiz.
d
32
ni d
31
+ d
12
= 10 + 3 = 13 bilan almashtiramiz va s
32
= 1 ni o‗rnatamiz.
D
1
va S
1
matritsalar quyidagi shaklga ega:
7.17-rasm. D
1
va S
1
matritsalari
2-qadam. k = 2 deb olamiz; D
1
matritsada yetakchi satr va ustun ajratilgan.
Uchburchak operator juft ramka bilan ajratilgan D
1
va S
1
matritsalar elementlariga
qo‗llaniladi. Natijada D
2
va S
2
matritsalarini olamiz:
7.18-rasm. D
2
va S
2
matritsalar
3-qadam. k = 3 deb olamiz; D
2
matritsada yetakchi satr va ustun ajratilgan.
Uchburchak operator juft ramka bilan ajratilgan D
2
va S
2
matritsalar elementlariga
qo‗llaniladi. Natijada D
3
va S
3
matritsalarni olamiz:
59
7.19-rasm. D
3
va S
3
matritsalar
4-qadam. k = 4 deb olamiz, D
3
matritsada yetakchi satr va ustun ajratilgan.
D
4
va S
4
yangi matritsalarni olamiz:
7.20-rasm. D
4
va S
4
matritsalari
5-qadam. k = 5 olamiz, D
4
matritsadagi yetakchi satr va ustun ajratilgan. Bu
qadamda hech qanday amallarni bajarmaymiz; hisoblashlar yakunlandi.
D
4
va S
4
yakuniy matritsalar istalgan tarmoqning ikkita tugunlari orasidagi
eng qisqa yo‗llarni aniqlash uchun zarur bo‗ladigan barcha ma‘lumotlarni o‗z
ichiga oladi. Masalan, 1- va 5-nchi tugunlar orasidagi eng qisqa masofa d
15
= 12 ga
teng bo‗ladi.
Mos marshrutlarni topish uchun marshrutning ta‘kidlaymizki, (i, j) segment
faqat s
ij
= j bo‗lganda (i, j) qirradan iborat bo‗ladi. Aks holda, i va ј tugunlar
kamida bitta oraliq tugun orqali ulanadi. Masalan, s
15
= 4 va s
45
= 5 bo‗lganligi
sababli, avval 1 va 5 tugunlar orasidagi eng qisqa yo‗l 1→ 4 → 5 bo‗ladi. Ammo
s
14
4 ga teng emasligi sababli, 1 va 4 tugunlar ma‘lum bir yo‗lda bitta qirra bilan
60
ulanmagan (lekin dastlabki tarmoqda ular to‗g‗ridan-to‗g‗ri bog‗langan bo‗lishi
mumkin).
Keyin 1 va 4 - tugunlar orasidagi oraliq tugunlarni aniqlash kerak bo‗ladi. s
14
= 2 va s
24
= 4 ga egamiz, shuning uchun 1→4 marshrutni 1→ 2→ 4 marshrut bilan
almashtiramiz. s
12
= 2 va s
24
= 4 bo‗lganligi sababli, boshqa oraliq tugunlar mavjud
emas. Marshrutning ma‘lum segmentlarini birlashtirish bilan nihoyat 1 tugundan 5
tugungacha bo‗lgan eng qisqa yo‗l - 1→ 2→ 4→ 5 ni olamiz. Bu yo‗lning uzunligi
12 kilometrga teng.
| 