“Floyd algoritmi” mavzusidagi

1.2.Qisqa yo‘lni izlash algoritmi.
Tarmoqda qisqa yo„lni izlashning ikki algoritmi bilan tanishamiz. Ulardan biri siklga (takrorlanuvchi) ega tarmoq uchun, ikkinchisi siklga ega bo„lmagan tarmoq uchun.

1. 
   Deykstra algoritmi
   

2. 
   Floyd algoritmi
   

Deykstra algoritmi berilgan boshlang„ich tugun bilan tarmoqning istalgan tuguni o„rtasidagi qisqa yo„lni izlash uchun ishlab chiqilgan. Floyd algoritmi birmuncha umumiy bo„lib, u yordamida bir vaqtning o„zida tarmoqning istalgan ikki tuguni orasidagi eng qisqa yo„lni topish mumkin.

Deykstra algoritmi. Ushbu algoritm bajarilishi jarayonida i-tugundan j-tugunga o„tishda tomonga nishon qo„shish protsedurasidan foydalaniladi. U_i orqali boshlang„ich 1-tugundan i-tugungacha bo„lgan eng qisqa yo„lni belgilaymiz. d_ij orqali i, j tomon uzunligi belgilaymiz.

Tugunlar nishoni Deykstra algortmida ikki tipda: vaqtinchalik va doimiy bo„ladi. Agar berilgan tugungacha bo„lgan birmuncha qisqa yo„l topilsa, vaqtinchalik nishon boshqa bir vaqtinchalik nishon bilan almashtiriladi.

Boshlang„ich tugundan berilgan tuguncha boshqa eng qisqa yo„l qolmaganiga ishonch hosil qilingandan so„ng, vaqtinchalik nishon maqomi doimiyga almashtiriladi.
Algoritmning hisoblash sxemasi quyidagicha.