1. Algoritmning maqsadi va tushunchasi haqida tushuntirish Deykstra algoritmi qanday ishlaydi?

4.
 Primning minimal tejamkor daraxti (MST). 
Men ko'rgan yagona farq shundaki, Prim algoritmi minimal xarajatlar 
chegarasini saqlaydi, Dijkstra algoritmi esa manba uchidan hozirgi verteksgacha 
bo'lgan umumiy xarajatlarni saqlaydi. 
Dijkstra sizga xarajatlar minimal bo'lishi uchun manba tugunidan maqsad 
tuguniga yo'l beradi. Ammo Prim algoritmi sizga barcha tugunlar ulanishi va 
umumiy xarajat minimal bo'lishi uchun minimal daraxtni beradi. 
Oddiy so'zlar bilan: 
Shunday qilib, agar siz bir nechta shaharlarni ulash uchun poezdni 
joylashtirmoqchi bo'lsangiz, siz Prim algosidan foydalanasiz. Ammo agar siz bir 
shahardan ikkinchisiga imkon qadar ko'proq vaqt tejashni istasangiz, Dijkstra 
algidan foydalangan bo'lar edingiz. 
Ikkalasi ham xuddi shunday umumiy algoritm yordamida bajarilishi 
mumkin: 
Inputs: 

---

G: Graph 
s: Starting vertex (any for Prim, source for Dijkstra) 
f: a function that takes vertices u and v, returns a number 
Generic(G, s, f) 
Q = Enqueue all V with key = infinity, parent = null 
s.key = 0 
While Q is not empty 
u = dequeue Q 
For each v in adj(u) 
if v is in Q and v.key > f(u,v) 
v.key = f(u,v) 
v.parent = u 
Prim, pass f = w(u, v)va Dijkstra dovoni uchun f = u.key + w(u, v). 
Yana bir qiziq tomoni shundaki, Generic-dan yuqorida "Bread" birinchi 
qidirishni (BFS) amalga oshirishi mumkin, ammo bu haddan tashqari ko'p bo'lishi 
mumkin, chunki qimmat ustunlik navbati aslida talab qilinmaydi. Yuqoridagi 
umumiy algoritmni BFS-ga o'tkazish uchun, f = u.key + 1barcha og'irliklarni 1 ga 
bog'lash bilan bir xil (masalan, BFS A nuqtadan B ga o'tish uchun zarur bo'lgan 
minimal qirralarni beradi). 
Uni vaqt bo'yicha baholash
Algoritmning uni vaqt boʻyicha baholash (runtime analysis) muhimligi, 
algoritmlarning ishlashining necha martaqadir ishlayotgani vaqti bilan bog'liqdir. 
Bu aniq vaqt yuzaga kelishi odatda algoritmda ishlatilgan operatsiyalar va 
ma'lumotlar soni bilan bog'liqdir. Uni vaqt boʻyicha baholash, algoritmning ishga 
tushirish va ishlayotgan vaqtni o'rganish uchun foydali bo'ladi. Bu, algoritmning 
ish faoliyatida ishlatilgan yodgorlik (memory) xotirasiga, har bir ishlatilgan 
elementning qiymati va uning jadvallashuvi, shuningdek, ishlatilgan operatsiyalar 
kabi ko'plab faktorlarni ko'rsatishi mumkin. 
Uni vaqt bo'yicha baholash, algoritmlarni boshqarishning va aniq 
yechim topishning bir qismi sifatida ham ishlatiladi. Masalan, bir dasturda eng 
yaxshi algoritmlardan foydalanish uchun, algoritmlarning ishlash vaqtlarini 
solishtirishdan foydalanish mumkin. Shuningdek, bir algoritmning uni vaqt 
bo'yicha baholashini tushunish, o'zida o'zgarishlarni qilish uchun to'g'ri vaqtida, 
qo'shimcha resurslar ishlatishni belgilash imkonini beradi. 
Bular bilan birga, algoritmlarni tartibga solishda, ularning uni vaqt 
bo'yicha baholashini bilish katta ahamiyatga ega bo'ladi, shunda o'zgarishlarni 
qilish va hujjatlar bilan ishlashda aniq vaqtni belgilash mumkin bo'ladi. 
Biz kruskalning 
minimal 
tejamkorlik 
daraxti 
uchun 
algoritmini muhokama qildik . Kruskalning algoritmi singari, Prim algoritmi 
ham ochko'z algoritmdir . U bo'shashgan daraxtdan boshlanadi. G'oya ikkita 
vertikal to'plamni ushlab turishdir. Birinchi to'plamda allaqachon MST-ga 
kiritilgan uchlari mavjud, ikkinchisida esa hali mavjud bo'lmagan uchlari 
mavjud. Har qadamda, u ikkita to'plamni bog'laydigan barcha qirralarni ko'rib 

---

chiqadi va bu qirralarning minimal og'irligini tanlaydi. Yonni tanlaganingizdan 
so'ng, u chetning boshqa oxirgi uchini MST o'z ichiga olgan to'plamga o'tkazadi. 
Grafikdagi ikkita uch uchini bog'laydigan qirralar guruhi grafik nazariyasida 
kesilgan deb nomlanadi . Shunday qilib, Prim algoritmining har bir bosqichida biz 
kesmani topamiz (ikkita to'plam, bittasida allaqachon MST kiritilgan va boshqa 
vertikal qismlar mavjud), kesmaning eng kam og'irligini tanlang va bu uchni MST 
Set-ga qo'shing. (allaqachon kiritilgan uchlarini o'z ichiga olgan to'plam).