21-maruza Graflarda eng qisqa yo‘lni aniqlash algoritmlari. Graflarda eng qisqa yo’lni aniqlashning Ford – Belmann va Deykstra algoritmlari. - N cho'qqisi va m cheti bo'lgan yo'naltirilgan og'irlikli G grafigi berilsin va ba'zi bir uchi v ko'rsatilsin. v cho'qqisidan boshqa barcha cho'qqilargacha bo'lgan eng qisqa yo'llarning uzunliklarini topish talab qilinadi. Dijkstra algoritmidan farqli o'laroq, bu algoritm manfiy og'irlikdagi qirralarni o'z ichiga olgan grafiklarga ham tegishli. Biroq, agar grafik manfiy tsiklni o'z ichiga olgan bo'lsa, unda, albatta, ba'zi cho'qqilarga eng qisqa yo'l mavjud bo'lmasligi mumkin (eng qisqa yo'lning og'irligi minus cheksizlikka teng bo'lishi kerakligi sababli); ammo, bu algoritm salbiy og'irlik tsikli mavjudligini bildirish uchun o'zgartirilishi mumkin, yoki hatto tsiklning o'zini chiqarishi mumkin.
Algoritm ikki amerikalik olimning nomini oldi: Richard Bellman va Lester Ford. Ford aslida bu algoritmni 1956-yilda boshqa matematik muammoni oʻrganayotganda ixtiro qildi, uning kichik muammosi grafikdagi eng qisqa yoʻlni topish edi va Ford bu muammoni hal qiluvchi algoritmning konturini berdi. Bellman 1958 yilda eng qisqa yo'lni topish muammosiga bag'ishlangan maqola chop etdi va bu maqolada u bugungi kunda biz bilgan algoritmni aniq aytib berdi. - Algoritm ikki amerikalik olimning nomini oldi: Richard Bellman va Lester Ford. Ford aslida bu algoritmni 1956-yilda boshqa matematik muammoni oʻrganayotganda ixtiro qildi, uning kichik muammosi grafikdagi eng qisqa yoʻlni topish edi va Ford bu muammoni hal qiluvchi algoritmning konturini berdi. Bellman 1958 yilda eng qisqa yo'lni topish muammosiga bag'ishlangan maqola chop etdi va bu maqolada u bugungi kunda biz bilgan algoritmni aniq aytib berdi.
Algoritmning tavsifi - Algoritmning tavsifi
- Biz grafikda manfiy og'irlik tsikli mavjud emas deb taxmin qilamiz. Salbiy tsiklning holati quyida alohida bo'limda ko'rib chiqiladi. Algoritm ishlab chiqilgandan so'ng, masalaning javobini o'z ichiga olgan d[0 \ldots n-1] masofalar massivini olaylik. Ishning boshida biz uni quyidagi tarzda to'ldiramiz: d[v] = 0 va d[] ning boshqa barcha elementlari cheksizlik ∞ ga teng.
Do'stlaringiz bilan baham: |
