Maslaning qo’yilishi

Amalga oshirish

Shunday qilib Deykstra algoritmi iteratsiyadan iborat. Harbir iteratsiyada qiymat eng kichik bo’lgan hali ko’rilmagan uch tanlanadi. Bu uch ko’rilgan uchlar ro’yxatiga kiritladi va bu uchdan chiquvchi harbir uch bo’yicha relaksatsiya tekshiriladi va har bir qirra bo’yicha massiv qiymatini yaxshilashga harakat qilinadi.

Algoritmning ishlash vaqti quyidagicha hisoblaymiz:

• 
  marta hali ko’rilmagan uchlar orasida eng kichik li uchni topamiz, ya’ni uch ichidan.
  
• 
  marta relaksatsiyaga urinidh amalga oshiriladi
  

Bu amallarni oddiy amalga oshirishda, uchni izlash uchun operatsiya, bitta relaksatsiya uchun esa— operatsiya ketadi. Algoritmning natijaviy asimptotikasi: