Mavzu: Floyd-Uorshell algoritmi

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

Algoritm

Ikkala holatda ham d ^k _ij ning qiymatini ko'rib chiqaylik - to'g'ri! Ikkala holatda ham k-1 uchun d qiymatining yig'indisi, demak d uchun boshlang'ich (k = 0) qiymatlar mavjud bo'lsa, biz barcha keyingi k qiymatlar uchun d ni hisoblashimiz mumkin. Va biz k = 0 uchun d qiymatlarini bilamiz, bu grafik qirralarning og'irligi / narxi, ya'ni oraliq tugunlarsiz birikmalar.

K = n (n - vertikallarning soni) uchun biz d juftlarning barcha juftlari uchun optimal qiymatlarni olamiz.

K-1 dan k gacha ko'tarilganda d ^k _ik uchun qanday qiymatni _saqlaymiz ? 1 va 2 holatlarning minimal qiymatlari bo'yicha, ya'ni biz eski yo'l yoki qo'shimcha verteks qo'shilishi kerak bo'lgan yo'l arzonroq bo'lishiga qaraymiz.

Soxta kod

Va nihoyat, algoritmning o'zi. Grafik namoyishni qo'shilishlarning matritsasi sifatida ishlatamiz .

Eng qisqa masofa Matritsa D Avvaliga - siz ko'rib turganingizdek, algoritm juda oddiy ⁰ boshlanganda , dastlab u D, biz k qiymatini oshirish va masofa matrisinde qayta aylanishi bilan, matrisi bilan bir vaqtga to'g'ri keladi ⁰ biz D olish ¹ D, ¹ D - ² va shuning uchun K uchun = n.

Agar biron-bir ikki vertikalning o'rtasida qirralar bo'lmasa, u holda ulashgan matritsada ba'zi katta sonlar yozilgan (bu grafikdagi har qanday yo'l uzunligidan kattaroq bo'lishi kerak); keyin bu qirrani olish har doim ham noqulay bo'ladi va algoritm to'g'ri ishlaydi. To'g'ri, agar biz maxsus choralarni ko'rmasak, unda agar chiziqlar grafasida salbiy og'irlik bo'lsa, ∞-1, ∞-2 va boshqalar shakllari raqamlari bo'lsa, bu albatta albatta mos keladigan narsalar orasida bo'lishini anglatadi. cho'qqilarga umuman yo'l yo'q. Shuning uchun, agar grafikada salbiy qirralar bo'lsa, Floyd algoritmini "yo'l yo'q" bo'lgan holatlardan o'tishni qilmaslik uchun yozgan ma'qul.

Misol