Internet va axborot kommunikatsiyasi fakulteti

O`ZBEKISTON RESPUBLIKASI
OLIY VA O’RTA MAXSUS TA’LIM VAZIRLIGI

Farg’ona shahridagi Koreya xalqaro universiteti

페르가나 한국국제대학교


INTERNET VA AXBOROT KOMMUNIKATSIYASI FAKULTETI
국제통상학과
2-kurs talabasi Aribjanov Ziyovuddin Qamariddin o’g’lining
2학년 ㅡㅡㅡㅡㅡㅡ
“Algoritm” fanidan

“Eng qisqa yo’lini topish” mavzusida tayyorlagan

Mustaqil ishi (과제)

Topshirilgan sana(과제 제출일) :
Baho(점수) :
O’qituvchi(교수명) : E.Kodirov
Talaba ID (학번) : 2122141053

Mavzu: Deykstra algoritmi va uni amalda qoʼllanishi.
Reja:
Kirish

1. 
   Diykstra algoritmi
   
2. 
   Diykstra algoritmi qanday ishlaydi. Dijkstra algoritmi
   
3. 
   Diykstra algoritmini amalga oshirish
   

Xulosa
Foydalanilgan adabiyotlar ro`yxati

Kirish
Bu algoritm grafiklar boʻyicha algoritm boʻlib, uni 1959-yilda golland olimi E.Dijkstroy ixtiro qilgan. Algoritm grafikning bir cho'qqisidan qolgan barcha nuqtalarigacha bo'lgan eng qisqa masofani topadi va faqat manfiy og'irlikdagi qirralari bo'lmagan grafiklar uchun ishlaydi.
Har bir cho'qqiga og'irlik beriladi - bu boshlang'ich cho'qqidan berilgangacha bo'lgan yo'lning og'irligi. Bundan tashqari, har bir cho'qqi tanlanishi mumkin. Agar cho'qqi tanlangan bo'lsa, undan boshlang'ich cho'qqigacha bo'lgan yo'l eng qisqasi, agar bo'lmasa, u vaqtinchalik. Grafikni aylanib o'tib, algoritm har bir cho'qqi uchun marshrutni hisoblab chiqadi va agar u eng qisqa bo'lib chiqsa, cho'qqini tanlaydi. Ushbu cho'qqining og'irligi yo'lning og'irligiga aylanadi. Berilgan cho'qqining barcha qo'shnilari uchun algoritm og'irlikni ham hisoblab chiqadi, shu bilan birga ularni hech qanday sharoitda ta'kidlamaydi. Algoritm o'z ishini yakunlaydi, yakuniy cho'qqiga etadi va tortishadi eng qisqa yo'l oxirgi cho'qqining og'irligiga aylanadi.