Tarmoqda eng qisqa masofani topish masalasi (dyekstr algoritmi) - Информатика и ИТ - Презентации

Информация о документе

Цена	3000UZS
Размер	1.1MB
Покупки	0
Дата загрузки	07 Ноябрь 2026
Расширение	pptx
Раздел	Презентации
Предмет	Информатика и ИТ

Tarmoqda eng qisqa masofani topish masalasi (dyekstr algoritmi)

Купить

TARMOQDA ENG QISQA
MASOFANI TOPISH MASALASI
(DYEKSTR ALGORITMI)

Dijkstra
algoritmi •
Dijkstra algoritmi berilgan cho'qqidan
qolgan barcha nuqtalarga minimal
yo'lni topish algoritmidir.
•
Ushbu algoritm og'irlikdagi
yo'naltirilmagan grafik misolida
ko'rsatiladi.

Algoritm tahlili
Dastlab, grafikning barcha cho'qqilari asl
cho'qqigacha bo'lgan masofani
tavsiflovchi biron bir belgini oladi. Bu
masofa ma'lum emas, shuning uchun biz
masofa hali ham juda katta raqam deb
taxmin qilamiz.
Yo'l boshlanadigan cho'qqi nol bilan
belgilanadi.
Qayta ishlangan uchlarini ham
belgilaymiz.

Algoritm tahlili.
•
Algoritm qayta ishlangan cho'qqining qo'shnilarini chetlab o'tadi.
•
Qo'shnilarning har biriga masofa ishlov beriladigan yorliqning yig'indisi va chekkaning
qo'shnisiga og'irligi sifatida hisoblanadi. Qabul qilingan qiymat qo'shni cho'qqining yorlig'i
bilan taqqoslanadi va agar olingan qiymat kamroq bo'lsa, u holda bu qiymat qo'shni
cho'qqiga tayinlanadi.
•
Qo'shnilardan o'tgandan so'ng, qayta ishlangan tepalik qayta ishlangan deb belgilanadi.
•
Yangi qayta ishlangan cho'qqi allaqachon qayta ishlanganiga eng yaqin bo'lganidek
qidiriladi. Bunday holda, yangi qayta ishlangan cho'qqi ishlov berilmasligi kerak.
•
O'tish barcha uchlari qayta ishlanmaguncha davom etadi.

Algoritmning ishi. 1-qadam
V1 cho'qqisini qayta ishlagandan so'ng , v2 , v3 va v5
tepalik belgilarining qiymatlari o'zgardi:
0+7 = 7 < 1 000 000, shuning uchun teg v2 = 7
0+9 = 9 < 1 000 000, shuning uchun v3 = 9
0+4 = 4 < 1 000 000, shuning uchun v5 = 4 yorlig'i
Vertex v1 qayta ishlangan deb belgilangan.
Keyin algoritm eng yaqin v5 uchini topadi va uni qayta
ishlashni boshlaydi.

Algoritmning ishi. 2-qadam
v5 tuguniga ishlov berilgandan so'ng v3 tugun
yorlig'ining qiymati o'zgardi:
4+2 = 6 < 9, shuning uchun v3 = 6 belgisini qo'ying
Vertex v5 qayta ishlangan deb belgilangan.
Algoritm yana eng yaqin qayta ishlanmagan v3 uchini
topadi va uni qayta ishlashni boshlaydi.

Algoritmning ishi. 3-qadam
uchini qayta ishlagandan so'ng , v2 va v4 cho'qqi
belgilarining qiymatlari quyidagicha:
v2 yorlig'i o'zgarmaydi
6+11 = 17 < 1 000 000, shuning uchun v4 = 17 yorlig'i
Vertex v3 qayta ishlangan deb belgilangan.
Algoritm yana eng yaqin qayta ishlanmagan v2 uchini
topadi va uni qayta ishlashni boshlaydi.

Algoritmning ishi. 4-qadam
Vertex v2 ni qayta ishlagandan so'ng, vertex label v4
qiymati:
7+12 = 19 > 17, shuning uchun v4 yorlig'i o'zgarmaydi
Vertex v2 qayta ishlangan deb belgilandi.
Algoritm yana eng yaqin qayta ishlanmagan v4 uchini
topadi va uni qayta ishlashni boshlaydi.

Algoritmning ishi. 4-qadam
Vertex v4 da ishlov berilmagan qo'shni uchlari yo'q,
shuning uchun u qayta ishlangan deb belgilangan.
Grafikni aylanib o'tish tugallandi, algoritm o'z ishini
yakunladi.
v1 dan v2-v4 gacha

Tarmoqda eng qisqa masofani topish masalasi (dyekstr algoritmi)

Купить

Похожие документы
Scratch dasturlash muhiti
Shaxsning ta'lim, tarbiyasi va rivojlanishida pedagogik dasturiy vositalari
Takrorlanuvchi algoritmlar
Tarmoqlanuvchi algoritmlar
Targ‘ibot dasturi Hayvonlarga nisbatan mehr-shafqatni oshirish