Mavzu: Floyd-Uorshell algoritmi

Matritsani birinchi qayta hisoblashi - bitta qiymat o'zgaradi, ruxsat etilgan uchlari to'plamining "1" tepasiga qadar kengayishi tufayli biz "4" vertikalidan "2" ga arzonroq usulda erishdik.

d ^k _ij = min (d ^k-1 _ij ; d ^k-1 _ik + d ^k-1 _kj )

d ¹ ₄₂ = min (d ⁰ ₄₂ , d ⁰ ₄₁ + d ⁰ ₁₂ )

d ¹ ₄₂ = min (4, -1)

Ikkinchi qaytarish, p uchun qiymat yaxshilandi ₄₃

Ish vaqti va xotiradan foydalanishni tahlil qilish

Matritsalarni saqlash uchun algoritm O (n ³ ) xotirasini talab qiladi . Biroq, matrislerden soni osonlik ikki qismga bo'lish mumkin, hatto bir keraksiz matristen qayta yozishni yoki har safar d dan indeksi K olishdan tomonidan ikki o'lchovli matritsasi borib ^k _ij . Tez-tez ishlatiladigan eng yaxshi variant bu qo'shni matritsaga to'g'ridan-to'g'ri yozishdir, keyin biz qo'shimcha xotiraga ehtiyoj sezmaymiz, garchi agar biz asl matritsani zudlik bilan qayta yozsak, qo'shimcha ravishda algoritmni to'g'ri ko'rsatishimiz kerak, chunki klassik akademik isbot faqat oldingi iteratsiyaning matritsasi bo'lgan taqdirdagina haqiqiydir. o'zgarmaydi.

Ishlash vaqtiga kelsak - 1 dan n gacha bo'lgan uchta ichki tsikl - Θ (n ³ ).