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

Chiqish natijasi: 
Vertex manbadan masofa 
0 0 
1 4 
2 12 
3 19 
4 21 
5 11 
6 9 
7 8 
8 14 
Izohlar: 
1) Kod eng qisqa masofani hisoblaydi, ammo yo'l to'g'risidagi ma'lumotni 
hisoblamaydi. Ota-onalar massivini yaratamiz, masofa yangilanganida ota-
ona massivini yangilaymiz 
(masalan, primning 
bajarilishi kabi ) 
va 
undan 
foydalanib, manbadan turli balandliklargacha eng qisqa yo'lni ko'rsatamiz. 
2) Kod yo'naltirilmagan grafik uchun, xuddi shu dijkstra funktsiyasi 
yo'naltirilgan grafikalar uchun ham ishlatilishi mumkin. 
3) Kod manbadan barcha vertikallarga eng qisqa masofani topadi. Agar bizni 
manbadan bitta maqsadgacha bo'lgan qisqa masofaga qiziqish bildirsa, tanlangan 
minimal masofa uchi nishonga teng bo'lganda biz halqa sindirishimiz mumkin 
(algoritmning 3.a qadam). 
4) Amalga oshirishning vaqt murakkabligi - O (V ^ 2). Agar kirish grafigi 
qo'shni ro'yxat yordamida taqdim etilsa , uni ikkilik to'plash yordamida O (E log 
V) 
ga 
kamaytirish 
mumkin. Qarang 
qo'shnilik ro'yxati vakolatxonasi uchun Dijkstra ning Algoritm batafsil ma'lumot 
uchun. 
5) Dijkstraning algoritmi og'irligi qirralari salbiy bo'lgan grafikalar uchun 
ishlamaydi. Salbiy 
vazn 
qirralariga 
ega 
grafikalar 
uchun Bellman-Ford 

---

algoritmidan foydalanish mumkin, yaqin orada biz uni alohida post sifatida ko'rib 
chiqamiz. 
Prim algoritmi grafika uchun barcha tugunlarni bog'laydigan va barcha 
tugunlarni 
bog'laydigan 
daraxtlar 
orasida 
eng 
kam 
xarajat 
keltiradigan daraxt bo'lgan minimal grafik daraxtini quradi . Biroq, MSTdagi har 
qanday ikkita tugun orasidagi yo'lning uzunligi asl grafikdagi ushbu ikki tugun 
orasidagi eng qisqa yo'l bo'lmasligi mumkin. MSTlar foydali bo'ladi, masalan, agar 
siz grafikadagi tugunlarni elektr energiyasini eng kam xarajat bilan ta'minlash 
uchun jismonan o'tkazmoqchi bo'lsangiz. Ikkala tugun orasidagi yo'l uzunligi eng 
maqbul bo'lmasligi muhim emas, chunki siz ularni bog'lab qo'yishingizni istaysiz. 
Dijkstra algoritmi ba'zi bir manbali tugunlardan boshlab eng qisqa yo'l 
daraxtini quradi . Qisqa yo'l daraxti - bu grafikadagi barcha tugunlarni 
qaytariladigan manba tuguniga bog'laydigan va har qanday yo'lning grafikadagi 
boshqa tugungacha bo'lgan uzunligi minimallashtirilgan xususiyatdir. Bu 
foydalidir, masalan, agar siz biron bir muhim muhim joyga etib borishga imkon 
beradigan darajada yo'l tarmog'ini qurmoqchi bo'lsangiz. Biroq, eng qisqa yo'l 
daraxti minimal daraxt bo'lishi kafolatlanmaydi va eng qisqa yo'lli daraxtning 
chekkalari xarajatlari MST narxidan ancha katta bo'lishi mumkin. 
Yana bir muhim farq algoritmlarning qaysi grafik turlari ustida ishlashiga 
bog'liq. Prim algoritmi faqat yo'naltirilmagan grafiklar ustida ishlaydi, chunki MST 
tushunchasi 
grafiklarning 
yo'naltirilmaganligini 
anglatadi. (Yo'naltirilgan 
grafikalar uchun "minimal tejamkorlik" deb nomlangan narsa bor, ammo ularni 
topish algoritmlari ancha murakkab). Dijkstraning algoritmi yo'naltirilgan 
grafikalarda yaxshi ishlaydi, chunki eng qisqa daraxt daraxtlarini chindan ham 
yo'naltirish mumkin. Bunga qo'shimcha ravishda, Dijkstra algoritmi salbiy 
qirralarni o'z ichiga olgan grafiklarda to'g'ri echimni ta'minlamaydi , Prim esa 
algoritmi bunga qodir.