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

Amalga oshirish:

• Amalga oshirish:

Salbiy tsikl mavjud bo'lganda, algoritmning n ta takrorlanishidan so'ng masofalar minusgacha borishi mumkinligi sababli (ko'rinishidan, -2 ^ n tartibli manfiy raqamlargacha), bunday holatlarga qarshi kodda qo'shimcha choralar ko'rildi. butun son to'lib ketishi:

• Salbiy tsikl mavjud bo'lganda, algoritmning n ta takrorlanishidan so'ng masofalar minusgacha borishi mumkinligi sababli (ko'rinishidan, -2 ^ n tartibli manfiy raqamlargacha), bunday holatlarga qarshi kodda qo'shimcha choralar ko'rildi. butun son to'lib ketishi:

Yuqoridagi amalga oshirish ba'zi bir boshlang'ich v cho'qqisidan erishish mumkin bo'lgan salbiy tsiklni qidiradi; ammo, algoritm oddiygina grafikda har qanday salbiy tsiklni izlash uchun o'zgartirilishi mumkin. Buning uchun biz barcha d[i] masofalarni cheksizlikka emas, nolga tenglashtirishimiz kerak - go'yo biz bir vaqtning o'zida barcha cho'qqilardan eng qisqa yo'lni qidirayotgandek; bu salbiy tsiklni aniqlashning to'g'riligiga ta'sir qilmaydi.

• Yuqoridagi amalga oshirish ba'zi bir boshlang'ich v cho'qqisidan erishish mumkin bo'lgan salbiy tsiklni qidiradi; ammo, algoritm oddiygina grafikda har qanday salbiy tsiklni izlash uchun o'zgartirilishi mumkin. Buning uchun biz barcha d[i] masofalarni cheksizlikka emas, nolga tenglashtirishimiz kerak - go'yo biz bir vaqtning o'zida barcha cho'qqilardan eng qisqa yo'lni qidirayotgandek; bu salbiy tsiklni aniqlashning to'g'riligiga ta'sir qilmaydi.