Jonson algoritmi

Jonson algoritmining uchta asosiy qismi
Jonson algoritmining ishlashini algoritmni quyidagi uchta asosiy qismga bo'lish orqali osongina tushunish mumkin.
• Asosiy uchini qo'shish
• Qirralarni qayta ishlash
• Barcha juftliklar uchun eng qisqa yo'lni topish
Endi biz Jonson algoritmining uchta asosiy qismining har biri bilan batafsil tanishamiz. Keling, Jonson algoritmining ishlashini misol bilan tushunaylik.
Quyidagi rasmda ko'rsatilganidek, a, b, c va d bo'lgan to'rtta qirraga ega bo'lgan G qirrasi bilan yo'naltirilgan grafigini ko'rib chiqing. Bizning maqsadimiz berilgan G grafigidagi har bir juft qirra orasidagi eng qisqa yo'lni hisoblashdir.

Har bir qirra juftligi orasidagi eng qisqa yo'lni hisoblash uchun har bir qirra bilan bevosita bog'langan asosiy qirrani (quyidagi rasmda S qirra) qo'shish g'oyasi hisoblanadi. Boshqacha qilib aytganda, yangi qo'shilgan S tayanch qirrasidan har bir qirraga chiqish vazni nolga teng. Ushbu bosqichda bizning grafigimiz manfiy vaznli qirralarini o'z ichiga olganligi sababli, biz Bellman-Ford algoritmini qo'llaymiz.

Yangi qo'shilgan asosiy uchi bilan o'zgartirilgan graf quyidagi rasmda ko'rsatilgan G' bo'lsin. Endi yuqorida o'zgartirilgan G' grafigi uchun Bellman-Ford algoritmini qo'llaganimizdan so'ng, biz asosiy qirradan boshqa barcha qirralargacha bo'lgan eng qisqa masofani olamiz, bu quyidagicha bo'ladi.


Bu erda D(S,V) - S qirradan V qirragacha bo'lgan eng qisqa masofa.
Qirralarni vaznini yangilash
Jonson algoritmi qirralarni qayta tortish texnikasidan foydalanadi.
Qirra vaznini yangilash - bu quyidagi ikkita maqsadni amalga oshirish uchun qirra vaznni o'zgartirish jarayonidir.
1. Grafdagi barcha juft u, v qirralar uchun, agar ma’lum bir yo’l qirra vaznini yangilashdan oldin o’sha qirralar orasidagi eng qisqa yo’l bo’lsa, qirra vaznini yangilagandan keyin ham u tugunlar orasidagi eng qisqa yo’l bo’lishi kerak.
2. Grafdagi barcha qirralar uchun (u, v) og'irlik (u, v) manfiy bo'lmasligi kerak. Qirralarni vaznini o’zgartiramiz, chunki G grafdagi barcha qirralarning og'irligi manfiy bo'lmasa, biz barcha qirralar juftligi orasidagi eng qisqa yo'lni Deykstra algoritmini har bir qirradan bir marta ishga tushirish orqali topishimiz mumkin, bu ko'proq. Bellman-Ford algoritmini qo'llashdan ko'ra samaraliroq.
Endi qirralarning og'irligi W ning yangi to'plami qirralarning vazni o’zgarishi natijasida quyidagi muhim xususiyatlarga javob berishi kerak.
1. U, v ∈ V qirralarining barcha juftligi uchun og’irlik funksiyasi yordamida u dan v gacha bo’lgan eng qisqa yo’l W vazn funksiyasi yordamida ham u dan v gacha bo’lgan eng qisqa yo’ldir.
2. Barcha qirralar uchun (u, v) yangi vazn W (u, v) manfiy emas.
Endi biz barcha qirralarning bu masofalarini S asosiy qirradan olganimiz sababli, biz S asosiy qirrasini olib tashlaymiz va quyidagi formuladan foydalanib qirralarni qayta tortamiz.
Uchburchak tengsizligidan foydalanib, biz bor
D(S,v) <= W(u, v) + D(S,u)
Shunday qilib, yuqoridagi tenglamadan foydalanib, biz qayta tortish tenglamamizni quyidagicha aniqlashimiz mumkin.
W(u, v) = W(u, v) + D(S,u) - D(S,v)
Bu yerda W(u,v) - u,v uchlari orasidagi chetning asl vazni va D(S,V) - S qirradan V qirragacha bo'lgan eng qisqa masofa.
Endi biz yuqoridagi formuladan foydalanib, yangi og'irliklarni hisoblaymiz.
W(u, v) = W(u, v) + D(S,u) - D(S,v)
a dan b gacha qirra uchun yuqoridagi formulaga u=a va v=b qo‘ysak, olamiz
W(a, b) = W(a, b) + D(S,a) - D(S,b)
W(a, b) = -5 + (-3) - (-8)
W(a, b) = 0
Yuqoridagi formulaga u=b va v=c qo‘ysak, b dan c gacha bo‘lgan qirraga yetamiz
W(b, c) = W(b, c) + D(S,b) - D(S,c)
W(b, c) = 6 + (-8) - (-2)
W(b, c) = 0
d dan c gacha bo'lgan qirra uchun yuqoridagi formulaga u=d va v=c qo'ysak, natijada
W(d, c) = W(d, c) + D(S,d) - D(S,c)
W(d, c) = 3 + 0 - (-2)
W(a, b) = 5

a dan d gacha qirra uchun yuqoridagi formulaga u=a va v=d qo‘ysak, natijada

W(a, d) = W(a, d) D(S,a) - D(S,d)
W (a, d) = 4 + (-3) -0
W(a, d) = 1
Yuqoridagi formulaga u=c va v=a qo‘ysak, c dan a ga vaznga erishamiz
W(c, a) = W(c, a) + D(S, c) - D(S,a)
W(c, a) = 2 + (-2) - (-3)
W(c, a) = 3
Yuqoridagi formulaga u=b va v=a qo‘yib, b ning a qirrasi uchun olamiz
W(b, a) = W(b, a) + D(S, b) - D(S,a)
W(b, a) = 7 + (-8) - (-3)
W(b, a) = 2
Yuqoridagi formulaga u=d va v=a qo‘ysak, d dan a ga yangi vaznli qirraga erishamiz
W(d, a) = W(d, a) + D(S, d) - D(S,a)
W(d, a) = -3 + 0 - (-3)
W(d, a) = 0
Quyidagi rasmda qirralari qayta tortilgan graf ko'rsatilgan.