TARMOQDA ENG QISQA MASOFANI TOPISH MASALASI (DYEKSTR ALGORITMI)

Yuklangan vaqt:

10.08.2023

Ko'chirishlar soni:

0

Hajmi:

1126.177734375 KB

Ko'chirib olish

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)

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.

Grafik misol

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.

O'xshashlar

QISQA KO’PAYTIRISH FORMULALARI

Yo’nalish azimuti va masofani o’lchash

Bit algoritmi

M5. TARMOQDA AXBOROT TIZIMLARINI HIMOYALASH ALGORITMLARI

Qismga ko’ra sonning o’zini topish