Jonson algoritmi

Jonson algoritmi
Jonson algoritmi grafdagi eng qisqa yo'l juftligini topish uchun ishlatiladi. Biz Jonson algoritmidan foydalanib, qirra og'irlikdagi yo'naltirilgan grafdagi barcha qirralar juftlari orasidagi eng qisqa yo'llarni topishimiz mumkin. Jonson algoritmi Deykstra algoritmidan ham, Bellman-Ford algoritmidan ham foydalanadi. Jonson algoritmi manfiy vaznli graflarda ham barcha juftliklarning eng qisqa yo'llarini topishi mumkin. Grafdagi eng qisqa yo'lni topish uchun biz Floyd Uorshall algoritmidan foydalanishimiz mumkin bo'lsa-da, Jonson algoritmi Floyd Uorshall algoritmiga qaraganda vaqt murakkabligi jihatidan ancha samaraliroq.
Qo'llash doirasi:
• Ushbu kurs ishida biz ma'lumotlar tuzilmalarida Jonson algoritmi bilan tanishamiz.
• Jonson algoritmi grafdagi barcha juftlikdagi eng qisqa yo‘lni topishning samarali usulidir.
• Biz ushbu algoritmning ishlashi va bu algoritmni qanday amalga oshirishimiz mumkinligini ko'rib chiqamiz.
• Jonson algoritmining murakkabligi
o Vaqt murakkabligi - O(V^2log V + VE)O(V2logV+VE)
Vaziyatni ko'rib chiqaylik, yo'l qurilish firmasiga bir nechta qishloqlarni yo'l tarmog'i orqali bog'lash uchun tender topshirilgan, shunda odamlar bir qishloqdan ikkinchisiga minimal vaqt ichida yetib borishi mumkin. Yo'l tarmog'ini graf sifatida tasvirlashimiz mumkin, bunda qishloqlarni graf tugunlari shaklida va qishloqlar orasidagi yo'lni graf qirralari shaklida tasvirlash mumkin.
Endi bu muammo grafdagi barcha tugun juftlari orasidagi minimal masofani topishga qisqartirildi.
Berilgan G grafigidagi barcha juft eng qisqa yoʻlni topish uchun Jonson algoritmi qoʻllaniladi. Jonson algoritmi Deykstra algoritmidan ham, Bellman-Ford algoritmidan ham foydalanadi. Jonson algoritmi manfiy vaznli graflarda ham eng qisqa yo'lni topishi mumkin. Berilgan grafni qayta tortish va grafdagi sikllarni aniqlash texnikasidan foydalangan holda manfiy vaznli yo'q qilish uchun Bellman-Ford algoritmidan foydalanadi. Endi biz ushbu yangi, o'zgartirilgan grafni yaratganimizdan so'ng, ushbu algoritm berilgan graf uchun barcha qirralar juftligi orasidagi eng qisqa yo'lni hisoblash uchun Deykstraning eng qisqa yo'l algoritmidan foydalanadi. Jonson algoritmining natijasi asl grafdagi har bir juft qirra orasidagi eng qisqa yo'llar to'plamidir. Yuqoridagi qadamlar quyida batafsil muhokama qilinadi.