21-maruza Graflarda eng qisqa yo‘lni aniqlash algoritmlari. Graflarda eng qisqa yo’lni aniqlashning Ford – Belmann va Deykstra algoritmlari

Ford-Bellman algoritmi ushbu tsiklning barcha cho'qqilari va undan erishish mumkin bo'lgan cho'qqilar orasida cheksiz bo'shashishi mumkinligini tushunish oson. Shuning uchun, agar fazalar soni n-1 bilan cheklanmagan bo'lsa, u holda algoritm cheksiz ishlaydi, bu cho'qqilargacha bo'lgan masofalarni doimiy ravishda yaxshilaydi. Bu yerdan biz manfiy vaznga erishish mumkin bo'lgan tsikl mavjudligining mezonini olamiz: agar n-1 fazalardan keyin biz yana bitta fazani bajarsak va unda kamida bitta bo'shashish sodir bo'lsa, u holda grafik v dan erishish mumkin bo'lgan manfiy og'irlik tsiklini o'z ichiga oladi; aks holda, bunday tsikl yo'q.

• Ford-Bellman algoritmi ushbu tsiklning barcha cho'qqilari va undan erishish mumkin bo'lgan cho'qqilar orasida cheksiz bo'shashishi mumkinligini tushunish oson. Shuning uchun, agar fazalar soni n-1 bilan cheklanmagan bo'lsa, u holda algoritm cheksiz ishlaydi, bu cho'qqilargacha bo'lgan masofalarni doimiy ravishda yaxshilaydi. Bu yerdan biz manfiy vaznga erishish mumkin bo'lgan tsikl mavjudligining mezonini olamiz: agar n-1 fazalardan keyin biz yana bitta fazani bajarsak va unda kamida bitta bo'shashish sodir bo'lsa, u holda grafik v dan erishish mumkin bo'lgan manfiy og'irlik tsiklini o'z ichiga oladi; aks holda, bunday tsikl yo'q.

Bundan tashqari, agar bunday tsikl topilsa, Ford-Bellman algoritmini shunday o'zgartirish mumkinki, u bu tsiklni o'zi unga kiritilgan tepaliklar ketma-ketligi sifatida chiqaradi. Buning uchun n-bosqichda gevşeme sodir bo'lgan x cho'qqisining sonini eslab qolish kifoya.

• Bundan tashqari, agar bunday tsikl topilsa, Ford-Bellman algoritmini shunday o'zgartirish mumkinki, u bu tsiklni o'zi unga kiritilgan tepaliklar ketma-ketligi sifatida chiqaradi. Buning uchun n-bosqichda gevşeme sodir bo'lgan x cho'qqisining sonini eslab qolish kifoya.
• Bu cho'qqi yoki manfiy og'irlik tsiklida yotadi yoki undan erishish mumkin. Tsiklda yotishi kafolatlangan cho'qqini olish uchun, masalan, x cho'qqisidan boshlab, ajdodlar orqali n marta o'tish kifoya. Tsiklda yotgan cho'qqining y raqamini olganimizdan so'ng, biz o'sha cho'qqiga qaytgunimizcha, ajdodlar bo'ylab bu cho'qqidan borishimiz kerak (va bu albatta sodir bo'ladi, chunki salbiy og'irlik tsiklidagi bo'shashishlar aylanada sodir bo'ladi. ).