Jonson algoritmi

Barcha juftliklar uchun eng qisqa yo'lni topish
Endi qirralarning og'irligini qayta o'lchaganimizdan so'ng, biz manfiy bo'lmagan og'irliklarga ega bo'lgan barcha qirralarga ega bo'ldik, shuning uchun biz berilgan G grafgi uchun barcha juft eng qisqa yo'lni topish uchun Deykstra algoritmini qo'llashimiz mumkin.
Har bir qirra juftligi uchun eng qisqa yo'lni olgandan so'ng, algoritm oxirida aniq yo'l og'irligi qaytarilishi uchun ushbu yo'l og'irliklarini dastlabki yo'l og'irliklariga aylantirish juda muhim bo'ladi. Buni oddiygina qayta tortish jarayonini o'zgartirish orqali amalga oshirish mumkin. Nihoyat, har bir juft qirradan eng qisqa yo'lni ifodalovchi matritsani olamiz.
Endi, Deykstra algoritmini har bir tepada alohida qo'llaganimizdan so'ng, biz barcha juftliklar orasidagi eng qisqa masofani olamiz, bu quyidagicha.
A ni manba qirrasi sifatida ko'rib chiqing, a dan boshqa barcha qirralargacha bo'lgan eng qisqa masofa quyidagicha.
D(a, a) = 0
D(a, b) = W(a, b)
D(a, b) = 0
D(a, c) = W(a, b) + W(b, c)
D(a, c) = 0 + 0 = 0
D(a, d) = W(a, d)
D(a, d) = 1
b ni manba qirrasi sifatida ko'rib chiqing, b dan boshqa barcha qirralargacha bo'lgan eng qisqa masofa quyidagicha.
D(b, a)= W(b, a)
D(b, a)= 2
D(b, b)= 0
D(b, c) = W(b, c)
D(b, c) = 0
D(b, d)=W(b,a) +W(a, d)
D(b, d) = 2 + 1 = 3
c ni manba qirrasi sifatida ko'rib chiqing, c dan boshqa barcha qirralargacha bo'lgan eng qisqa masofa quyidagicha.
D(c, a) = W(c,a)
D(c, a) = 3
D(c, b) = W(c, a) +W(a, b)
D(c, b) = 3 + 0
D(c, b) = 3
D(c, c) = 0
D(c, d) = W(c, a) + W(a,d)
D(c, d) = 3 + 1
D(c, d) = 4
d ni manba qirrasi sifatida ko'rib chiqing, d dan boshqa barcha qirralargacha bo'lgan eng qisqa masofa quyidagicha.
D(d, a) = W(d, a)
D(d, a) = 0
D(d, b) = W(d, a) + W(a, b)
D(d, b) = 0 + 0 = 0
D(d, c) = W(d, a) + W(a, b) + W(b, c)
D(d, c) = 0 + 0 + 0 = 0
D(d, d) = 0

Yuqoridagi hisob-kitoblardan biz barcha juftliklar orasidagi eng qisqa masofani jadval shaklida ifodalashimiz mumkin. Quyidagi jadval har bir juft qirra orasidagi masofani ko'rsatadi.

Yo'naltirilgan qirra og'irlikdagi grafda har qanday u qirradan v qirragacha bo'lgan masofa va aksincha, a qirradan b qirragacha bo'lgan masofa 0 birlik bo'lishi yoki bo'lmasligi mumkin, lekin b qirradan a qirragacha bo'lgan masofa 22 ga teng ekanligini unutmang. birliklar.

Qayta tortish isboti
Endi biz grafning chetlarini qayta tortdik. Shunday qilib, biz grafani qayta tortish aslida qirralarning og'irliklarining umumiy yig'indisini o'zgartirmasligini isbotlashimiz kerak. Qayta tortilgan grafda biz bir xil h(s)h(s) − h(t)h(t) ni qo‘shamiz, bunda h(s)h(s) va h(t)h(t) ning uzunligi. yangi qo'shilgan asosiy S qirrasidan mos ravishda s va tt qirralariga eng qisqa yo'l. ularga qo'shilgan tugunlarning s va t jufti orasidagi barcha yo'llarda.
Keling, qayta tortish kontseptsiyasi qirralarning og'irliklarining haqiqiy umumiy yig'indisini saqlab qolishini matematik tarzda qanday isbotlashimiz mumkinligini ko'rib chiqaylik. Grafning ikkita qirrasi orasidagi yo'l (s,t)(s,t) bo'lsin. Qayta tortilgan grafdagi WW vazni quyidagi ifoda bilan ifodalanadi:
Quyidagi ifoda p ning asl og'irlikdagi og'irligidir.
(w(s,p1)+h(s)-h(p1))+(w(p1,p2)+h(p1)-h(p2))+...+(w(pn,t)+ h(pn)-h(t))
Har bir +h(pi) tomonidan bekor qilinadi -
h(pi) oldingi qavs ichidagi ifodada, shuning uchun biz W uchun quyidagi ifodani qoldiramiz:
(w(s,p1)+w(p1,p2)+...+w(pn,t))+h(s)-h(t)
Shunday qilib, biz aniq ko'rishimiz mumkinki, qayta tortish har bir yo'lning og'irligiga ss qirrasidan t qirragacha bo'lgan har bir yo'lning og'irligiga bir xil miqdorni qo'shadi, shuning uchun biz aytishimiz mumkinki, yo'l dastlabki grafdagi eng qisqa yo'ldir, agar u eng qisqa yo'l bo'lib qolsa. grafni qayta tortish.
Endi salbiy tomonlar mavjud bo'lmasa, biz Deykstra algoritmi tomonidan topilgan yo'llarning optimalligiga aminmiz. Dastlabki grafdagi masofalarni qayta tortish o'zgarishini teskari o'lchash yo'li bilan qayta o'lchangan grafdagi Deykstra algoritmi tomonidan hisoblangan masofalardan hisoblash mumkin.
• Dastlab biz o'zgartirilgan G' grafigini yaratamiz, unda asosiy qirrani dastlabki G grafigiga qo'shamiz.
• G' grafigida manfiy og'irlik sikli bor yoki yo'qligini tekshirish uchun Bellman-Ford ALgoritmini qo'llaymiz.
• Graf manfiy og'irlik siklidan xoli bo'lsagina, barcha juftlik eng qisqa yo'lni topishimiz mumkin.
• Grafning manfiy og'irlik siklidan xoli ekanligini aniqlaganimizdan so'ng, Bellman-Ford algoritmi yordamida har bir qirra uchun eng qisqa yo'lni hisoblaymiz.
• Shuningdek, biz asosiy qirrani olib tashlash orqali grafning chetlarini qayta tortamiz, bu esa grafda har qanday manfiy og'irlikdagi qirralarning yo'qligiga ishonch hosil qiladi.
• Endi bu bosqichda biz qirralarni qayta tortganimizdan beri grafigimiz manfiy og‘irlikdagi qirralardan xoli bo‘lishi kafolatlanadi, shuning uchun grafdagi har bir qirra jufti orasidagi eng qisqa masofani topish uchun grafdagi har bir qirra uchun Deykstra algoritmini qo‘llaymiz. bu bizning orzu qilgan maqsadimiz.

Jonson algoritmini amalga oshirish

• Avval biz quyidagi kodda Altered_weights bilan ifodalangan o'zgartirilgan og'irliklarni saqlash uchun ro'yxat tuzamiz.
• O'zgartirilgan og'irliklarni topish uchun Bellman-Ford algoritmini qo'llaymiz.
• Quyidagi kodda Altered_Graph bilan ko'rsatilgan o'zgartirilgan grafimiz Altered_weights dan iborat bo'ladi va u salbiy og'irlikdagi qirralardan xoli bo'ladi.
• Endi bu bosqichda bizning Altered_Graph salbiy og'irlikdagi qirralardan xoli bo'lishi kafolatlanganligi sababli, biz xohlagan maqsadimiz bo'lgan grafdagi har bir qirra jufti orasidagi eng qisqa masofani topish uchun Altered_Graphdagi har bir qirra uchun Deykstra algoritmini qo'llaymiz. .
Quyida Python-da Jonson algoritmini amalga oshirish ko'rsatilgan.
Dastur kodi joyi

Chunki Jonson algoritmida talab qilinadigan asosiy qadamlar:

1. Bir marta chaqiriladigan Bellman-Ford algoritmi.
2. V marta deb ataladigan Deykstra algoritmi, bu erda V - berilgan G grafdagi uchlari soni.
Biz bilamizki, Vaqt murakkabligi:
• Bellman Ford algoritmi O(VE).O(VE).
• Deykstra algoritmi O(VLogV)O(VLogV).
Shunday qilib, umumiy vaqt murakkabligi O(V^2log V + VE)O(V2logV+VE) bo'lib, o'rtacha holat.
To'liq graf bo'lsa, Jonson algoritmining vaqt murakkabligi Floyd Warshell algoritmi bilan bir xil bo'lishini bilish juda qiziq.
Shuni ta'kidlash kerakki, Jonson algoritmining eng yomon vaqt murakkabligi
O(V^3 + V*E), chunki Deykstra algoritmi O(V^2) vaqtni oladi.

Jonson algoritmining qo'llanilishi

Jonson algoritmining turli xil ilovalari mavjud, ulardan ba'zilari quyidagilardir.
1. Jonson algoritmining eng ko'p qo'llaniladigan qo'llanilishi bu yo'llar tarmog'idir.
2. Ma'lumotlar paketlarini jo'natish uchun optimal yo'lni tanlash uchun Tarmoq marshrutlash uchun ishlatiladi.
3. Eng qisqa yo'l va eng kam tirbandlik bilan eng yaxshi marshrutni aytish uchun Haydash yo'nalishlarida ham qo'llaniladi.
4. Ushbu algoritm logistika maqsadida turli firmalar tomonidan transport xarajatlarini minimallashtirish uchun keng qo'llaniladi.