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

E'tibor bering, Ford-Bellman algoritmi xuddi shu mantiq bo'yicha ishlaydi: bir cho'qqigacha bo'lgan eng qisqa masofa allaqachon hisoblab chiqilgan deb faraz qilsak, u boshqa cho'qqigacha bo'lgan eng qisqa masofani yaxshilashga harakat qiladi. Shuning uchun, yaxshilanish vaqtida biz faqat p [] da eslab qolishimiz kerak, bu yaxshilanish qaysi cho'qqidan kelgan. Bu erda Ford-Bellman ilovasi berilgan t cho'qqisiga yo'lni tiklash bilan birga:

• E'tibor bering, Ford-Bellman algoritmi xuddi shu mantiq bo'yicha ishlaydi: bir cho'qqigacha bo'lgan eng qisqa masofa allaqachon hisoblab chiqilgan deb faraz qilsak, u boshqa cho'qqigacha bo'lgan eng qisqa masofani yaxshilashga harakat qiladi. Shuning uchun, yaxshilanish vaqtida biz faqat p [] da eslab qolishimiz kerak, bu yaxshilanish qaysi cho'qqidan kelgan. Bu erda Ford-Bellman ilovasi berilgan t cho'qqisiga yo'lni tiklash bilan birga:

Bu erda biz birinchi navbatda t cho'qqisidan boshlab ajdodlar bo'ylab o'tamiz va butun yo'lni \rm yo'llari ro'yxatida saqlaymiz. Ushbu ro'yxat v dan t gacha bo'lgan eng qisqa yo'lni ishlab chiqaradi, lekin teskari tartibda, shuning uchun biz uni \rm teskari deb chaqiramiz va keyin chiqaramiz.

• Bu erda biz birinchi navbatda t cho'qqisidan boshlab ajdodlar bo'ylab o'tamiz va butun yo'lni \rm yo'llari ro'yxatida saqlaymiz. Ushbu ro'yxat v dan t gacha bo'lgan eng qisqa yo'lni ishlab chiqaradi, lekin teskari tartibda, shuning uchun biz uni \rm teskari deb chaqiramiz va keyin chiqaramiz.

Algoritmning isboti Birinchidan, biz darhol ta'kidlaymizki, v dan etib bo'lmaydigan cho'qqilar uchun algoritm to'g'ri ishlaydi: ular uchun d[] yorlig'i cheksizlikka teng bo'lib qoladi (chunki Ford-Bellman algoritmi s dan erishish mumkin bo'lgan barcha cho'qqilarga ba'zi yo'llarni topadi va va boshqa barcha cho'qqilarda bo'shashish bir marta ham sodir bo'lmaydi). Keling, quyidagi fikrni isbotlaylik: i fazalaridan so'ng Ford-Bellman algoritmi uzunligi (qirralar soni bo'yicha) i dan oshmaydigan barcha eng qisqa yo'llarni to'g'ri topadi.

• Algoritmning isboti Birinchidan, biz darhol ta'kidlaymizki, v dan etib bo'lmaydigan cho'qqilar uchun algoritm to'g'ri ishlaydi: ular uchun d[] yorlig'i cheksizlikka teng bo'lib qoladi (chunki Ford-Bellman algoritmi s dan erishish mumkin bo'lgan barcha cho'qqilarga ba'zi yo'llarni topadi va va boshqa barcha cho'qqilarda bo'shashish bir marta ham sodir bo'lmaydi). Keling, quyidagi fikrni isbotlaylik: i fazalaridan so'ng Ford-Bellman algoritmi uzunligi (qirralar soni bo'yicha) i dan oshmaydigan barcha eng qisqa yo'llarni to'g'ri topadi.