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

Ford-Bellman algoritmining o'zi bir necha bosqichlardan iborat. Har bir bosqichda grafikning barcha qirralari ko'rib chiqiladi va algoritm c qiymatining har bir chekkasi (a,b) bo'ylab bo'shashishni (bo'shashtirish, zaiflashtirish) bajarishga harakat qiladi. Bir chekka bo'ylab bo'shashish - d[b] qiymatini d[a] + c qiymati bilan yaxshilashga urinish. Aslida, bu biz b cho'qqisiga javobni chekka (a, b) va joriy javobni a cho'qqisiga qo'llash orqali yaxshilashga harakat qilayotganimizni anglatadi. Grafikdagi barcha eng qisqa yo'llarning uzunligini to'g'ri hisoblash uchun algoritmning n-1 bosqichlari etarli ekanligi da'vo qilinadi (yana manfiy og'irlikdagi tsikllar yo'q deb taxmin qilamiz). Olib bo'lmaydigan cho'qqilar uchun d[] masofa cheksizlik ∞ ga teng bo'lib qoladi.

• Ford-Bellman algoritmining o'zi bir necha bosqichlardan iborat. Har bir bosqichda grafikning barcha qirralari ko'rib chiqiladi va algoritm c qiymatining har bir chekkasi (a,b) bo'ylab bo'shashishni (bo'shashtirish, zaiflashtirish) bajarishga harakat qiladi. Bir chekka bo'ylab bo'shashish - d[b] qiymatini d[a] + c qiymati bilan yaxshilashga urinish. Aslida, bu biz b cho'qqisiga javobni chekka (a, b) va joriy javobni a cho'qqisiga qo'llash orqali yaxshilashga harakat qilayotganimizni anglatadi. Grafikdagi barcha eng qisqa yo'llarning uzunligini to'g'ri hisoblash uchun algoritmning n-1 bosqichlari etarli ekanligi da'vo qilinadi (yana manfiy og'irlikdagi tsikllar yo'q deb taxmin qilamiz). Olib bo'lmaydigan cho'qqilar uchun d[] masofa cheksizlik ∞ ga teng bo'lib qoladi.

Amalga oshirish Ford-Bellman algoritmi uchun boshqa koʻplab grafik algoritmlardan farqli oʻlaroq, grafikni barcha qirralarning yagona roʻyxati sifatida koʻrsatish qulayroqdir (n ta chekka roʻyxati – har bir choʻqqidan qirralar emas). Yuqoridagi amalga oshirishda chekka uchun \rm edge ma'lumotlar strukturasi o'rnatiladi. Algoritm uchun kirish ma'lumotlari n, m raqamlari, qirralarning ro'yxati e va boshlang'ich uchining soni v. Barcha tepalik raqamlari 0 dan n-1 gacha raqamlangan. Eng oddiy amalga oshirish \rm INF doimiysi "cheksizlik" sonini bildiradi - u barcha mumkin bo'lgan yo'l uzunliklaridan oshib ketadigan tarzda tanlanishi kerak.

• Amalga oshirish Ford-Bellman algoritmi uchun boshqa koʻplab grafik algoritmlardan farqli oʻlaroq, grafikni barcha qirralarning yagona roʻyxati sifatida koʻrsatish qulayroqdir (n ta chekka roʻyxati – har bir choʻqqidan qirralar emas). Yuqoridagi amalga oshirishda chekka uchun \rm edge ma'lumotlar strukturasi o'rnatiladi. Algoritm uchun kirish ma'lumotlari n, m raqamlari, qirralarning ro'yxati e va boshlang'ich uchining soni v. Barcha tepalik raqamlari 0 dan n-1 gacha raqamlangan. Eng oddiy amalga oshirish \rm INF doimiysi "cheksizlik" sonini bildiradi - u barcha mumkin bo'lgan yo'l uzunliklaridan oshib ketadigan tarzda tanlanishi kerak.