Axborotlashtirish texnologiyalari

M ta uch va N ta qirralardan iborat uzluksiz grafda V₀ uchidan W uchigacha Dist(W) masofani topish kerak. Qirralar uzunliklari A matrisa bilan berilgan deb hisoblaymiz.
Qadam 0. [uchlarni belgilash] – bu yerda V₀ uchini “aniqlangan” deb belgilaymiz, qolgan barcha uchlarini “aniqlanmagan” deb hisoblaymiz.
Qadam 1. [o’zgaruvchilarni inetsiallashtirish] – bu yerda
Dist(U):=A(V₀ ,U) – barcha G ga tegishli U uchlari uchun;
Dist(V₀):=0; Next:=V₀;
Qadam 2. [sikl]. While NEXT<>W do
Begin
Qadam 3. [“aniqlanmagan” uchgacha eng qisqa yo’lni yangilash]. Har bir “aniqlanmagan” U uchi uchun
Dist(U):=min(Dist(U):Dist(Next)+A(Next, U)).
Qadam 4. [“aniqlanmagan” uchgacha eng qisqa yo’lni tanlash]. Agar U barcha “aniqlanmagan” uchlari orasida Dist(U) masofasi eng kichik bo’lsa, uni “aniqlangan” deb belgilaymiz va NEXT:=U.
end.
Bu algoritmning va dasturning murakkabligini O(M²) ekanligini ko’rsatish mumkin.
Takrorlash ucun nazorat savollari


1. Qaysi mezonlar bo/yicha eng qisqa yo’llar masalalarini yechish mumkin?
2. Deykstra algoritmi nima uchun yaxshi hisoblanadi?
3. Algoritmni psevdokodda tavsiflashning qo’layligini ko’rsating
4. Deykstra algoritmining bahosi qanday?


Mustaqil ishlash uchun nazorat savollari:

1. 
   Algoritmni baholash uchun qo’llanishi mumkin bo’lgan mezonlarni tavsiflab bering.
   
2. 
   Vaqtli mezon bo’yicha baholash jarayoniga misollar ko’rsating.
   
3. 
   Hajmiy mezon bo’yicha baholash jarayoniga misollar ko’rsating.
   
4. 
   Eng qisqa yo’llarni topish masalasiga 3ta turli mezon bo’yicha yechim misollarini korsating.
   
5. 
   Deykstra algoritmidan farqli boshqa eng qisqa yo’llarni topadigan algoritmni tuzing.