|
Zbekiston respublikasi raqamli texnologiyalarni rivojlantirish vazirligi muhammad al-xorazmiy nomidagi
|
| bet | 3/3 | | Sana | 20.12.2023 | | Hajmi | 1,03 Mb. | | #125304 |
Bog'liq KT 2-TOPSHIRIQKeyingi qadamlar. Qolgan balandliklar uchun algoritmning qadamini takrorlaymiz. Bu mos ravishda 4- va 5-nchi balandliklar bo’ladi.
7.12- rasm. Deykstra algoritmini 4- va 5-nchi balandliklar bo‘yicha o‘tish grafi
Algoritmni bajarilishini tugatish. Algoritm hech bir balandlikka ishlov berish mumkin bo’lmaganda ishlashni tugatadi. Bu misolda barcha balandliklar o’chirilgan, ammo har qanday misolda ham shunday bo’ladi deb faraz qilish xato bo’ladi, ayrim balandliklar, agar ularga yetib borish imkoni bo’lmasa, o’chirilmay qolishi mumkin. Algoritmning natijasi oxirgi rasmdan ko’rinadi: 1-nchi balandlikdan 2-chi balandlikkacha bo’lgan eng qisqa yo’l 7 ni, 3-chi balandlikkacha yo’l – 9 ni, 4-chi balandlikkacha yo’l – 20 ni, 5-chi balandlikkacha yo’l – 20 ni, 6-chi balandlikkacha yo’l 11 ni tashkil etadi.
Жараён
|
Belgi
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
0
|
L
|
0
|
∞
|
∞
|
∞
|
∞
|
∞
|
∞
|
∞
|
Q
|
|
|
|
|
|
|
|
|
1
|
L
|
0
|
6
|
7
|
8
|
∞
|
∞
|
∞
|
∞
|
Q
|
|
1
|
1
|
1
|
|
|
|
|
2
|
L
|
0
|
6
|
7
|
8
|
∞
|
12
|
∞
|
∞
|
Q
|
|
1
|
1
|
1
|
|
3
|
|
|
3
|
L
|
0
|
6
|
7
|
8
|
12
|
12
|
∞
|
∞
|
Q
|
|
1
|
1
|
1
|
|
3
|
3
|
|
4
|
L
|
0
|
6
|
7
|
8
|
12
|
12
|
13
|
∞
|
Q
|
|
1
|
1
|
1
|
4
|
3
|
3
|
|
5
|
L
|
0
|
6
|
7
|
8
|
12
|
12
|
13
|
18
|
Q
|
|
1
|
1
|
1
|
6
|
3
|
3
|
6
|
|
| |
