Mavzu: Floyd-Uorshell algoritmi

Case 1. element k qilingan emas eng qisqa yo'l p kiritilgan _ij biz hech narsa qo'lga kiritdi va eng qisqa yo'l qiymati ekanini vositalari qo'shimcha tepalik nuqtasiga, qo'shib o'zgartirish hech narsa yo'q, deb, ^k _{etdi Ij} , o'z navbatida, o'zgargani yo'q

d ^k _ij = d ^k-1 _ij - ^k _o'sguncha qiymatni qabul qiling.


Case 2. element k eng qisqa yo'l p kiradi _Ij ruxsat yo'liga yangi tepalik nuqtasiga qo'shgandan so'ng, deb, eng qisqa yo'l o'zgardi va endi uch v orqali o'tadi qildi _k . Yangi usul qancha pul oladi?

Yangi qisqa yo'l uch v bo'linadi _k p ichiga _Chiqish va p _kJ , biz birinchi xususiyatidan foydalaning unga ko'ra, p _ik va p _{kJ bo'lgan} , shuningdek, V qisqa yo'llar _i v uchun _K va V dan _k v uchun _{, j} mos ravishda. Demak

d ^k _ij = d ^k _ik + d ^k _kj

Va bu yo'llardagi k oxirgi yoki boshlang'ich tugun bo'lgani uchun, u oraliq tugunlar to'plamiga kiritilmagan, shuning uchun uni undan olib tashlashingiz mumkin: