GRAFLAR ENG QISQA MASOFA TOPISH ALGORITMLAR
![“GRAFLAR ENG QISQA MASOFA TOPISH ALGORITMLAR”
mavzusida
Mundarija
Floyd Algoritmlari ........................................................................................................................................ 3
Haddan tashqari algoritmlar ........................................................................................................................ 5
Qaytish bilan qidirish. Ushbu usul chuqur qidirish uslubiga asoslangan. Qaytish bilan qidirish sinov va
xato usuli hisoblanadi ("keling, bu yo'nalishda borishga harakat qilaylik – bu ishlamaydi - qaytib keling
va boshqasiga harakat qilaylik"). Variantlarni qidirish chuqur qidirish usuli bilan amalga oshirilganligi
sababli, algoritm ish paytida daraxtdagi joriy yo'lni saqlash tavsiya etiladi. Bu yo'l bir yo'l suyakka
hisoblanadi.Bundan tashqari, bir qator Distga ehtiyoj bor, uning o'lchami grafikaning vertikalari soniga
mos keladi, bu har bir Vertex uchun dastlabki tepadan masofani saqlaydi. ............................................ 5
To'lqin algoritmi. Kenglik qidiruviga asoslangan bu ortiqcha algoritm ikki bosqichdan iborat: to'lqin
tarqalishi; teskari harakat. To'lqinning tarqalishi va hujayralar tashrif buyuradigan usulning qadam
raqami bilan belgilanadigan kenglikdagi qidiruv mavjud. Qaytish jarayonida, oxirgi tepadan boshlab,
minimal belgilar bilan hujayralarni kiritish yo'li bilan unga kiritilgan yo'lni tiklash (misol 45.4). Muhim
xususiyat shundaki, tiklanish oxiridan boshlanadi (boshidan bu ko'pincha mumkin emas). .................... 6
Graflar ustida amallar ............................................................................................................................ 19
Xulosa ........................................................................................................................................................ 22
Foydalanilgan adabiyotlar ......................................................................................................................... 23
Foydalanilgan Internet saytlar ................................................................................................................... 23](/data/documents/149bece6-5bcf-473f-815b-e3d80597b66a/page_1.png)
![Kirish
Qandaydir masalani xal etishga kirishishdan avval buning uchun eng yaxshi
uslub izlanadi va uni qay tarzda tavsiflash aniqlanadi. Boshqacha qilib aytganda, biz
doimo maqsadi ba’zi bir zaruriy natijaga erishishdan iborat, amallar ketma-ketligi
bilan berilgan turli-tuman qoidalarga duch kelamiz. Bunday amallarning ketma-
ketligi algoritm deb ataymiz.
Matematikada algoritmning murakkabligi, xal etish masalalari va ularni ishlab
chiqish prinsiplarini o’rganadigan maxsus “Algoritmlar nazariyasi” bo’limi xam
mavjud.
Algoritmlar nazariyasi – algoritmlarning umumiy xossalari, qonuniyatlari va
ularni tasvirlanishining turli-tuman formal modellarini o’rganish bilan shug’ullanadi.
Algoritm tushunchasini formallashtirish asosida ularning samaradorligi taqqoslash,
ularning ekvivalentligi tekshirish, qo’llanilish sohasini aniqlash mumkin.
Graflar nazariysida eng qisqa yo’lni aniqlash muhim klassik masalalaridan biri deb
hisoblanadi. Uni hisoblash va echimlarni topish uchun bir qancha algoritmlari
mavjud.
Eng qisqa yo’l masalasi (inglizchada – shortest path problem) – bu grafning ikkita
tugun orasidagi eng qichik yo’l (masofa, zanjir, marshrut) topish masalasidir,
qaysidaki yoylarning vaznlarining yig’indisi minimal qiymatga ega. Qisqa (oddiy)
zanjir geodezik zanjir ham aytiladi.
Ushbu masalani adabiyotlarda bir nechta boshqa nomlanishi ham uchratish mumkin:
minimal masofa masalasi, dilijans masalasi, qisqa masofa masalasi va boshqalar.
Grafda eng qisqa masofani topish masalasi yo’naltirilgan, yo’naltirilmagan va
aralash graflarda echimini aniqlash mumkin.](/data/documents/149bece6-5bcf-473f-815b-e3d80597b66a/page_2.png)
![Floyd Algoritmlari
Ushbu algoritm ba'zan Floyd-Warshell algoritmi deb ataladi. Floyd-Warshell
algoritmi 1962da Robert Floyd va Stiven Uorchell tomonidan ishlab chiqilgan
graflarda algoritmdir. Grafning barcha juftlari orasidagi eng qisqa yo'llarni topishga
xizmat qiladi. Floyd usuli to'g'ridan-to'g'ri qovurg'alarning ijobiy og'irliklari bo'lgan
ustunda, har qanday elementar bo'lmagan (1 qovurg'asidan ko'prog'ini o'z ichiga
olgan), eng qisqa yo'l boshqa eng qisqa yo'llardan iborat. Ushbu algoritm Dijkstra
algoritmiga nisbatan ancha keng tarqalgan, chunki har qanday ikki ustun o'rtasida
eng qisqa yo'llarnitopadi. Floyd algoritmida eng qisqa yo'llarning uzunligi
hisoblangan NxN matritsasi ishlatiladi. A[i,j] elementi, agar u erda chekka (i, j)
bo'lsa,yakuniy qiymatga ega bo'lgan va aks holda abadiylikka teng bo'lgan j ning
yuqori qismidan masofaga teng. Floyd Algoritmning asosiy g'oyasi. I, j, k ning uchta
tepasi bor va ular orasidagi masofa belgilanadi. Agar tengsizlik a[i,k]+a[k,j]<a[i,j]
bajarilsa, i->j yo'lini i->k->j bilan almashtirish tavsiya etiladi. Qadam 0. A0
masofasining dastlabki matritsasini va S0 vertexlarining ketma-ketligini aniqlang.
Har ikkala matritsaning har bir diagonali elementi 0ga teng, shuning uchun bu
elementlarning hisob-kitoblarda ishtirok etmasligini ko'rsatmoqda. K = 1 ga
ishonamiz. Asosiy qadam k. k satrini va k ustunini etakchi satr va etakchi ustun
sifatida belgilang. Yuqorida tavsiflangan AK-1 matritsasining barcha
elementlariga[i, j] almashtirishni ko'rib chiqamiz. Agar tengsizlik a[i,k]+a[k,j]<a[i,j],
(i\ne k, j\ne k, i\ ne j) bajarilsa, unda quyidagi harakatlar amalga oshiriladi:
A[i,k]+a[k,j] miqdori uchun A[i,j] elementining Ak-1 matritsasini almashtirish orqali
Ak matritsasini yarating] ; k g6a SK-1 element s[i,j] matritsasini almashtirish orqali
Sk matritsasini yarating. Shunday qilib, Floyd algoritmi n yinelemelerini qiladi, a
matritsasining i- yinelemesinden keyin, bu yo'llar birinchi dan i-chigacha bo'lgan
tepaliklardan o'tishi sharti bilan, har qanday ikki juftlik orasidagi eng qisqa
yo'llarning uzunligini o'z ichiga oladi. Har bir iteratsiya bo'ylab barcha juftlar ko'chib
o'tadi va ularning orasidagi yo'l i-tepa yordamida kamayadi.](/data/documents/149bece6-5bcf-473f-815b-e3d80597b66a/page_3.png)
![Misol 45.2. Floyd algoritmini namoyish qilish
// Floyd algoritm funktsiyasi tavsifi
void Floyd(int n, int **Graph, int **ShortestPath)
{ int i, j, k;
int Max_Sum = 0;
for ( i = 0 ; i < n ; i++ ) for ( j = 0 ; j < n ; j++ )
Max_Sum+= ShortestPath[i][j];
for ( i = 0 ; i < n ; i++)
if ( ShortestPath[i][j] == 0 && i!=j)
ShortestPath[i][j] = Max_Sum;
for ( k = 0 ; k <n;k++)
for ( i = 0 ; i < n; i++)
if ((ShortestPath[i][k] + ShortestPath[k][j])
ShortestPath[i][j] = ShortestPath[i][k] ;
Agar grafik yo'naltirilmagan bo'lsa, unda transformatsiyalar natijasida olingan
barcha matritsalar nosimmetrik bo'lib, shuning uchun faqat asosiy diagonaldan
yuqorida joylashgan elementlarni hisoblash kifoya.
Agar grafik qo'shni matritsasi bilan ifodalangan bo'lsa, unda bu algoritmning
ishlash vaqti o(n3) buyrug'iga ega, chunki u bir-biriga biriktirilgan uchta tsiklni o'z
ichiga oladi.](/data/documents/149bece6-5bcf-473f-815b-e3d80597b66a/page_4.png)
![Haddan tashqari algoritmlar
Bulkhead algoritmlari, odatda, optimal yechim topish uchun qidiruv
algoritmlari. Shu bilan birga, yechim asta-sekin ishlab chiqilgan. Bunday holda,
odatda, daraxt variantlarining ustunlarini qidirish haqida gap boradi. Bunday
ustunning tepalari oraliq yoki yakuniy variantlar bo'ladi va qovurg'alar variantlarni
loyihalash yo'llarini ko'rsatadi.Labirintdagi eng qisqa yo'lni topish vazifasi
misolida ustundagi qidiruv usullariga asoslangan juda ko'p algoritmlarni ko'rib
chiqing.
Muammo bayonoti.
O'tish va o'tkazilmaydigan hujayralardan tashkil topgan labirint mxn o'lchamli
a matritsasi bilan berilgan. Agar hujayra (i,j) o'tkazilsa, matritsaning elementi
a[i,j]=0. Aks holda, a [i,j]=\infty.Hujayradagi (1, 1) hujayradagi (m, n) eng qisqa
yo'lning uzunligini topish kerak.Aslida, qo'shni matritsa berilgan (faqat nollar
abadiylik bilan almashtiriladi va birliklar nolga teng). Labirint-bu grafik.Ushbu
vazifadagi variantlar daraxtining tepalari qafada boshlangan yo'llardir (1, 1).
Qovurg'alar-bu yo'llarning dizayni yo'lini ko'rsatadi va k va k+1 uzunliklarining
ikki yo'lini birlashtiradi, bu erda ikkinchi yo'l yana bir harakatning yo'lini birinchi
marta qo'shib olinadi.
Qaytish bilan qidirish. Ushbu usul chuqur qidirish uslubiga asoslangan. Qaytish
bilan qidirish sinov va xato usuli hisoblanadi ("keling, bu yo'nalishda borishga
harakat qilaylik – bu ishlamaydi - qaytib keling va boshqasiga harakat qilaylik").
Variantlarni qidirish chuqur qidirish usuli bilan amalga oshirilganligi sababli,
algoritm ish paytida daraxtdagi joriy yo'lni saqlash tavsiya etiladi. Bu yo'l bir yo'l
suyakka hisoblanadi.Bundan tashqari, bir qator Distga ehtiyoj bor, uning o'lchami
grafikaning vertikalari soniga mos keladi, bu har bir Vertex uchun dastlabki tepadan
masofani saqlaydi.](/data/documents/149bece6-5bcf-473f-815b-e3d80597b66a/page_5.png)
![Hozirgi hujayra (algoritm boshida – hujayra (1, 1) ). Agar hozirgi hujayra
uchun qo'shni qo'shni qo'shni bo'lsa, u yo'lda hali bormagan yo'lda yo'q bo'lsa,
unda biz yo'lda qo'shni qo'shamiz va hozirgi hujayradan qo'shni tayinlaymiz, aks
holda yo'lni olibtashlaymiz.
Yuqoridagi tavsif, bu usulning nima uchun qaytib kelishi bilan busting deb
atalishini aniq ko'rsatib beradi. Qaytish bu erda "Way out Way" operatsiyasi bilan
mos keladi, bu esa yo'l uzunligini 1gakamaytiradi.
Bulkhead bo'sh va orqaga qaytish uchun harakat qilganda tugaydi. Bunday
holatda qaytib kelish uchun hech qanday joyyo'q.
Way joriy yo'l, lekin ish jarayonida optimal yo'lni saqlash kerak. Algoritmni
takomillashtirish quyidagicha amalga oshirilishi mumkin: yo'lning uzunligi
OptimalWay uzunligidan kattaroq yoki teng bo'lishiga yo'l qo'ymang. Bunday
holda, agar biror variant topilsa, u albatta maqbul bo'lmaydi. Umuman olganda,
bunday takomillashtirish, hozirgi yo'l aniq bo'lmagan optimal holga kelganda, biz
orqaga qaytishimiz kerak degan ma'noni anglatadi. Algoritmning bu yaxshilanishi
ko'p hollarda bustni sezilarli darajada kamaytirishga imkon beradi.
To'lqin algoritmi. Kenglik qidiruviga asoslangan bu ortiqcha algoritm ikki
bosqichdan iborat: to'lqin tarqalishi; teskari harakat. To'lqinning tarqalishi va
hujayralar tashrif buyuradigan usulning qadam raqami bilan belgilanadigan
kenglikdagi qidiruv mavjud. Qaytish jarayonida, oxirgi tepadan boshlab, minimal
belgilar bilan hujayralarni kiritish yo'li bilan unga kiritilgan yo'lni tiklash (misol
45.4). Muhim xususiyat shundaki, tiklanish oxiridan boshlanadi (boshidan bu
ko'pincha mumkin emas).](/data/documents/149bece6-5bcf-473f-815b-e3d80597b66a/page_6.png)
![Misol 45.4. To'lqin algoritmini namoyish qilish
Qidiruv usuli bilan kenglikda qidirish, odatda, ma'lumotni saqlash uchun zarur
bo'lgan qo'shimcha xotirani talab qiladi, bu esa teskari yo'nalishda yo'lni qurish va
tashrif buyurilgan tepaliklarni belgilash uchun zarurdir. Biroq, u tezroq ishlaydi,
chunki u bir xil hujayradan bir martadan ko'proq tashrif buyurishdan butunlay
chiqarib tashlanadi.](/data/documents/149bece6-5bcf-473f-815b-e3d80597b66a/page_7.png)
![Dijkstra algoritmi
Dijkstra algoritmi eng qisqa yo’l algoritmi sifatida ham tanilgan. Bu grafning
tugunlari orasidagi eng qisqa yo’lni topish uchun ishlatiladigan algoritm. Algoritm
grafning barcha boshqa nuqtalaridan boshlang’ich manba cho’qqisidan eng qisqa
yo’llar daraxtini yaratadi. U minimal kenglikdagi daraxtdan farq qiladi, chunki ikkita
cho’qqi orasidagi eng qisqa masofa grafning barcha cho’qqilariga kiritilmasligi
mumkin. Algoritm manbadan minimal masofaga ega bo’lgan tugunlar to’plamini
qurish orqali ishlaydi. Bu erda Dijkstra algoritmi muammoni hal qilish va eng yaxshi
echimni topish uchun greedy yondashuvdan foydalanadi.
Grafdagi eng qisqa marshrutlar uchun ko’plab qidiruv algoritmlari bo’yicha, Habreda
faqatgina Floyd-Worschall algoritmining ta’rifi topildi. Ushbu algoritm grafaning
barcha vertikalari va ularning uzunligi o’rtasidagi eng qisqa yo’llarni topadi. Ushbu
maqolada Dijkstra algoritmining ishlash printsipini tasvirlab beraman. Bu algoritm
optimal yo’nalishlarni va ularning uzunligini ma’lum bir vertikal (manba) va grafning
boshqa vertikalari orasida topadi. Dijkstra algoritmi faqat ijobiy
og’irliklarga ega bo’lgan graf bilan ishlaydi. Algoritmni bajarayotganda, tugunlar
orasidagi eng qisqa yo’lni topish uchun qirralarning og’irliklarini qo’shish
kerak. Agar grafda salbiy og’irlik bo’lsa, algoritm ishlamay qoladi. Esda tutingki,
tugunni "tashrif buyurilgan" deb belgilaganingizdan so’ng, tugunga boradigan joriy
yo’l ushbu tugunga erishish uchun eng qisqa yo’ldir. Shuning uchun, agar sizda
salbiy og’irliklar bo’lsa, umumiy og’irlik kamaytirilsa, bu bosqichni o’zgartirishi
mumkin.
Bundan tashqari, Dijkstra algoritmini tushunishda savol tug’iladi:
bu BFSmi yoki DFSmi ? Xo’sh, u ham emas. Dijkstra algoritmi ustuvor birinchi
algoritmdir. Biroq, BFS va DFS algoritmlari o’rtasida ustuvorlik DFS emas, balki
BFS uchun ko’proq bo’ladi. Asosan, siz Dijkstra algoritmida BFS ning ba’zi muhim
tuzilmalarini topishingiz mumkin, ammo rostini aytganda, bu BFS algoritmidan
ancha ko’p.](/data/documents/149bece6-5bcf-473f-815b-e3d80597b66a/page_8.png)
![Deykstra algoritmini quydagi grafda ko’rib chiqsak.
Algoritm bosqichma-bosqich ishlaydi - har bir bosqichda u bitta cho’qqiga "tashrif
buyuradi" va teglarni qisqartirishga harakat qiladi. Algoritm barcha cho’qqilarga
tashrif buyurilgandan so’ng tugaydi.
Initializatsiya . A cho’qqi yorlig’ining o’zi 0 deb qabul qilinadi, boshqa
cho’qqilarning teglari cheksizlikka o’rnatiladi. Bu a dan boshqa cho’qqilargacha
bo’lgan masofalar hali ma’lum emasligini ko’rsatadi. Grafning barcha uchlari
ko’rilmagan deb belgilangan.
Algoritm bosqichi . Agar barcha cho’qqilarga tashrif buyurilgan bo’lsa, algoritm
tugaydi. Aks holda, hali tashrif buyurmagan cho’qqilardan minimal yorlig’i bo’lgan
u tepasi tanlanadi. Biz u oxirgi nuqta bo’lgan barcha mumkin bo’lgan marshrutlarni
ko’rib chiqamiz. U dan chekkalari olib boradigan cho’qqilar bu
cho’qqining qo’shnilari deyiladi. U ning har bir qo’shnisi uchun, tashrif buyurilgan
deb belgilanganlardan tashqari, joriy u yorlig’i qiymatlari va u ni ushbu qo’shni
bilan bog’laydigan chekka uzunligi yig’indisiga teng bo’lgan yangi yo’l uzunligini
ko’rib chiqing. Qabul qilingan uzunlik qiymati qo’shnining yorlig’i qiymatidan kam
bo’lsa, yorliq qiymatini qabul qilingan uzunlik qiymati bilan almashtiring. Barcha
qo’shnilarni hisobga olib, biz tepalikni belgilaymiz u tashrif buyurgandek va algoritm
qadamini takrorlang.
Misol
Rasmda ko’rsatilgan graf misolida algoritmning bajarilishini ko’rib chiqing.](/data/documents/149bece6-5bcf-473f-815b-e3d80597b66a/page_9.png)
![1-cho’qqidan qolgan barcha nuqtalargacha bo’lgan eng qisqa masofalarni topish talab
qilinsin.
Doiralar cho’qqilarni, chiziqlar ular orasidagi yo’llarni (grafning qirralarini)
ko’rsatadi. Doiralar cho’qqilarning raqamlarini ko’rsatadi, qirralarning tepasida
ularning "narxi" - yo’lning uzunligi ko’rsatilgan. Har bir cho’qqi yonida qizil yorliq
belgilanadi - bu cho’qqiga 1-cho’qqigacha bo’lgan eng qisqa yo’lning uzunligi.
Birinchi qadam . Bizning misolimiz uchun Dijkstra algoritmidagi qadamni ko’rib
chiqing. 1-vertex minimal yorlig’iga ega.2, 3 va 6 cho’qqilari uning qo’shnilaridir.](/data/documents/149bece6-5bcf-473f-815b-e3d80597b66a/page_10.png)
![1- cho ’ qqining birinchi qo ’ shnisi o ’ z navbatida 2- cho ’ qqidir , chunki unga boradigan
yo ’ lning uzunligi minimaldir . 1-cho’qqi orqali unga boradigan yo’l uzunligi 1-
cho’qqi yorlig’i qiymati va 1-dan 2-gacha bo’lgan chekka uzunligi yig’indisiga teng,
ya’ni 0 + 7 = 7. 2-cho’qqining joriy yorlig’i, cheksizlik, shuning uchun 2-cho’qqining
yangi yorlig’i 7 ga teng.
Biz shunga o’xshash operatsiyani 1-vertexning boshqa ikkita qo’shnisi - 3 va 6-chi
bilan bajaramiz.](/data/documents/149bece6-5bcf-473f-815b-e3d80597b66a/page_11.png)
![1-tugunning barcha qo’shnilari tekshiriladi. 1-cho’qqigacha bo’lgan joriy minimal
masofa yakuniy hisoblanadi va qayta ko’rib chiqilmaydi (bu haqiqatan ham shunday
ekanligi birinchi marta E. Dijkstra tomonidan isbotlangan ). Ushbu tepaga tashrif
buyurilganligini belgilash uchun uni grafdan kesib o’ting.
Ikkinchi qadam . Algoritm bosqichi takrorlanadi. Yana biz ko’rilmagan
cho’qqilarning "eng yaqinini" topamiz. Bu 7 deb belgilangan 2-cho’qqi.
Yana biz tanlangan cho’qqining qo’shnilarining teglarini kamaytirishga harakat
qilamiz, ular orqali 2-cho’qqi orqali o’tishga harakat qilamiz. Vertex 2 ning
qo’shnilari 1, 3 va 4 uchlaridir.
2 cho’qqisining birinchi (tartibda) qo’shnisi 1 cho’qqidir. Lekin u allaqachon tashrif
buyurilgan, shuning uchun biz 1-cho’qqi bilan hech narsa qilmaymiz.
2-cho’qqining keyingi qo’shnisi 3-vertexdir, chunki u kirmagan deb belgilangan
cho’qqilarning minimal yorlig’iga ega. Agar siz unga 2 dan o’tsangiz, unda bunday](/data/documents/149bece6-5bcf-473f-815b-e3d80597b66a/page_12.png)
![yo’lning uzunligi 17 ga teng bo’ladi (7 + 10 = 17). Ammo uchinchi cho’qqining joriy
yorlig’i 9 ni tashkil etadi, bu 17 dan kichik, shuning uchun yorliq o’zgarmaydi.
2-cho’qqining yana bir qo’shnisi 4-cho’qqidir. Agar siz unga 2-chi orqali o’tsangiz,
unda bunday yo’lning uzunligi 2-cho’qqigacha bo’lgan eng qisqa masofa va 2 va 4
cho’qqilar orasidagi masofa yig’indisiga teng bo’ladi, ya’ni , 22 (7 + 15 =
22) . 22<<math>\infty</math> bo’lgani uchun 4-cho’qqining yorlig’ini 22 ga
o’rnatdik.
2-vertexning barcha qo’shnilari ko’rib chiqildi, biz unga bo’lgan masofani muzlatib
qo’yamiz va tashrif buyurilgan deb belgilaymiz.](/data/documents/149bece6-5bcf-473f-815b-e3d80597b66a/page_13.png)
![Uchinchi qadam . Algoritmning qadamini 3-cho’qqini tanlab takrorlaymiz. Uni
“qayta ishlash”dan so’ng biz quyidagi natijalarni olamiz:
Keyingi qadamlar . Qolgan cho’qqilar uchun algoritmning qadamini
takrorlaymiz. Bular mos ravishda 6, 4 va 5 uchlari bo’ladi.](/data/documents/149bece6-5bcf-473f-815b-e3d80597b66a/page_14.png)
![Algoritmning bajarilishini yakunlash . Algoritm boshqa cho’qqilarni qayta ishlash
mumkin bo’lmaganda tugaydi. Bu misolda barcha cho’qqilar chizilgan, lekin har
qanday misolda shunday bo’ladi deb o’ylash xatodir - agar ularga etib bo’lmasa,
ya’ni graf uzilgan bo’lsa, ba’zi cho’qqilar chizilmagan holda qolishi
mumkin. Algoritmning natijasi oxirgi rasmda ko’rinadi: 1 cho’qqidan 2 gacha
bo’lgan eng qisqa yo’l 7, 3 gacha - 9, 4 - 20, 5 - 20, 6 – 11 bo ’ lishini ko ’ rishimiz
mumkin .
Grafdagi ma ’ lum bir manba tuguniga ega bo ’ lgan algoritm bu tugun bilan har bir
boshqa o ’ rtasidagi eng qisqa yo ’ lni topadi . Bundan tashqari , bitta tugunning eng
qisqa yo ’ llarini to ’ xtatish yo ’ li bilan bitta maqsadli tugunga maqsad tuguniga eng
qisqa yo ’ l aniqlanganidan keyin algoritm aniqlandi . Masalan , agar graf tugunlari](/data/documents/149bece6-5bcf-473f-815b-e3d80597b66a/page_15.png)
![shaharlarni ifodalasa va chekka xarajatlari to ’ g ’ ridan - to ’ g ’ ri yo ’ l bilan bog ’ langan
shaharlarning juftliklari o ’ rtasidagi masofani ifodalaydi ( oddiylik uchun , qizil
chiroqlar , ishlamaydigan belgilar , pullik yo ’ llar va boshqa to ’ siqlarni e ’ tiborsiz
qoldirish uchun ), Dijkstra algoritmi ishlatilishi mumkin Bir shahar va boshqa
shaharlarning eng qisqa yo ’ lini topish . Qisqa yo ’ l algoritmining keng tarqalgan
qo ’ llanilishi tarmoqni boshqarish protokollaridir , Shuningdek , Jonson kabi boshqa
algoritmlarda ham subroutin sifatida qo ’ llaniladi .
Dijkstra algoritmida musbat tamsay yoki haqiqiy sonlar bo’lgan etiketlar
ishlatiladi, bu aniq zaif tartibga solingan. Qiziqarli tomoni shundaki, Dijkstra aniq
belgilangan qisman tartibga ega bo’lgan va keyingi teglar (bir chekkadan o’tib
ketganda keyingi yorliq) monotonik ravishda kamaymaslik sharti bilan aniqlangan
teglardan foydalanish uchun umumlashtirilishi mumkin. Ushbu umumlashma
umumiy Dijkstra qisqa yo’l algoritmi deb ataladi.
Dijkstra algoritmini C++ dasturlash tilida ifodalanishi
#include<iostream>
#include<climits>
using namespace std;
int miniDist( int distance[], bool Tset[]) // minimal masofani topish
{
int minimum = INT_MAX,ind;
for ( int k = 0 ;k < 6 ;k ++ )
{
if (Tset[k] == false && distance[k] <= minimum)
{
minimum = distance[k];
ind = k;
}
}
return ind;](/data/documents/149bece6-5bcf-473f-815b-e3d80597b66a/page_16.png)
![}
void DijkstraAlgo( int graph[ 6 ][ 6 ], int src) // qo’shnilik matritsasi
{
int distance [ 6 ]; // har bir tugun uchun minimal masofani hisoblash uchun massiv
bool Tset[ 6 ]; // Har bir tugun uchun tashrif buyurilgan va tashrif buyurilmagan
belgilash uchun mantiqiy massiv
for ( int k = 0 ; k < 6 ; k ++ )
{
distance[k] = INT_MAX;
Tset[k] = false;
}
distance[src] = 0 ; // Manba tepasi masofasi 0 ga o’rnatiladi
for ( int k = 0 ; k < 6 ; k ++ )
{
int m = miniDist(distance,Tset);
Tset[m] = true;
for ( int k = 0 ; k < 6 ; k ++ )
{
// qo’shni vertex masofasini yangilash
If ( ! Tset [k] && graph[m][k] && distance[m] != INT_MAX && distance[m]
+ graph[m][k] < distance[k])
distance[k] = distance[m] + graph[m][k];
}
}
cout << " Vertex\t\tManba cho’qqisidan masofa " << endl;
for ( int k = 0 ; k < 6 ; k ++ )
{
char str = 65 + k;
cout << str << " \t\t\t " << distance[k] << endl;
}](/data/documents/149bece6-5bcf-473f-815b-e3d80597b66a/page_17.png)
![}
int main()
{
int graph[ 6 ][ 6 ] = {
{ 0 , 1 , 2 , 0 , 0 , 0 },
{ 1 , 0 , 0 , 5 , 1 , 0 },
{ 2 , 0 , 0 , 2 , 3 , 0 },
{ 0 , 5 , 2 , 0 , 2 , 2 },
{ 0 , 1 , 3 , 2 , 0 , 1 },
{ 0 , 0 , 0 , 2 , 1 , 0 }};
DijkstraAlgo(graph, 0 );
return 0 ;
}
Chiqish
Vertex Manbadan masofa
A 0 B 1 C 2 D 4 E 2 F 3
Vaqtning murakkabligi
Dijkstra algoritmining vaqt murakkabligi O(V^2) ga teng, bu erda V - grafdagi
cho’qqilar soni. Biroq, agar kirish grafigi qo’shnilik ro’yxati (grafni ko’rsatish usuli)
yordamida tasvirlangan bo’lsa, unda vaqt murakkabligini ikkilik to’p yordamida O(E
log V) ga kamaytirish mumkin.
Dijkstra algoritmining fazoviy murakkabligi O(V) ga teng, bu erda V - grafning
umumiy cho’qqilari soni. Buning sababi shundaki, biz ushbu barcha uchlarni
ro’yxatda chiqish sifatida saqlashimiz kerak.](/data/documents/149bece6-5bcf-473f-815b-e3d80597b66a/page_18.png)
![Graflar ustida amallar
Graflar ustida sodda amallar. Graflar ustida turli amallar bajarish mumkin,
masalan, graflarni birlashtirish, biriktirish, ko‘paytirish, grafni qismlarga ajratish
vahokazo. Eng sodda amallardan biri sifatida grafdan uchni olib tashlash amalini
keltirsa bo‘ladi. Bu amalni qo‘llash berilgan grafning uchlari to‘plamidan birorta
element yo‘qotishni (olib tashlashni) anglatadi. Natijada uchlari soni bittaga
kamaygan yangi graf hosil bo‘ladi. Albatta, bu amalni uchlari soni ikkitadan kam
bo‘lmagan graflar uchun qo‘llash mumkin bo‘lib, uni bajarish jarayonida olib
tashlanayotgan uch bilan birgalikda shu uchga insident bo‘lgan barcha qirralar
(yoylar) ham olib tashlanadi.
Eng sodda amallar qatoriga grafdan qirrani (yoyni) olib tashlash amalini ham
kiritish mumkin. Bu amalga ko‘ra berilgan grafning qirralari (yoylari) to‘plamidan
birorta element yo‘qotiladi (olib tashlanadi). Berilgan grafdan qirrani (yoyni) olib
tashlayotganda shu qirraga (yoyga) insident uchlarni grafda qoldirish ham yo‘qotish
ham mumkin. Bu yerda vaziyatga qarab ish yuritiladi.
Agar G graf karrali qirralarga ega bo‘lmasa, u holda uchlari G grafning
barcha uchlaridan iborat bo‘lgan shunday yagona G graf mavjudki, G grafdagi
barcha juft uchlar faqat va faqat G grafda qo‘shni bo‘lmagandagina qo‘shnidir.
Bunday G graf berilgan G grafning to‘ldiruvchi grafi deb ataladi.
Berilgan graf uchuun to’ldiruvchi grafni qurish jarayoni ham graflar ustida
bajariladigan amallar qatoriga kiritish mumkin. G garf uchun to’ldiruvchi grafni
qurish amalini qo’llash natijasida G graf hosil bo’ladi. Isbotlash mumkinki, G
munosabat o’rinlidir. Ggarflar ustida shunday amallarni bajarish mumkinki, ular
elementlari soni berilgan grafdagidan ko’proq bo’lgan boshqa garfalarning hosil
bo’lishiga olib keladi. Bunday amallar qatoriga uchni qo‘shish amali yoki qirrani
(yoyni) qo‘shish amalini kiritish mumkin.
Grafga yangi uchni qo‘shish turlicha usul bilan amalga oshirilishi mumkin.
Masalan, yangi v uchni berilgan grafga qo‘shish shu grafning v1 va v2 uchlariga
insedent bo’lgan qandaydir u qirrasiga qo’shish orqaliquyidagicha ikki bosqichda](/data/documents/149bece6-5bcf-473f-815b-e3d80597b66a/page_19.png)
![bajarilishi mumkin:
1). U qirra berilgan grafdan olib tashlanadi;
2).hosil bo’lgan grafga ikkita qirralar: v va v1 uchlariga insedent u1 qirra hamda v
va v2 uchlariga insedent qirra qo’shiladi.
Teorema.Agargrafdagiharbiruchninglokaldarajasiikkidankichik bo‘lmasa, u holda bu
graf siklgaega.
Grafning bog‘lamliligi tushunchasi. Agar oriyentirlanmagan grafda chetlari a va b
uchlardan iborat marshrut topilsa, bu a vab uchlar bog‘langan deb, marshrutning
o‘zi esa a va b uchlarni bog‘lovchi marshrut deb ataladi.
Tabiiyki, agar qandaydir uchlarni bog‘lovchimarshrutbirorai uchdanbir
Necha marta o‘tsa,uholdamarshrutningsiklikqisminiolibtashlab(bundasiklik
qismning o‘rniga marshrutda faqat ai uch qoldiriladi) yana o‘shauchlarni
bog‘lovchi oddiy zanjir ko‘rinishdagi marshrutni hosil qilish mumkin. Shuning
uchun, marshrut bilan bog‘langan uchlar doimo oddiy zanjir bilan ham bo‘glangan
bo‘ladi degan xulosagakelamiz.
Bir-biri bilan ustma-ust tushmaydigan ixtiyoriy ikkita uchlari bog‘langan graf
Agar grafdagi ikkita uchni biror oddiy zanjir bilan tutashtirish mumkin bo‘lsa,
u holda bu ikkita uch ekvivalent (bog‘langan) deyiladi. Bunday uchlar to‘plami
grafda ekvivalentlik munosabati bilan aniqlangan deb hisoblanadi. Uchlar to‘plami
bo‘yicha ekvivalentlik munosabatini inobatga olgan holda berilgan grafni
bog‘lamlilik komponentalari (qisqacha, komponentalari) deb ataluvchi bog‘lamli
qismlarning birlashmasi deb qarash mumkin. Bu yerda berilgan graf bog‘lamlilik
komponentalariga bo‘laklandi (ajratildi) deb aytish mumkin. Isbotlash mumkinki,
har qanday graf o‘zining bog‘lamlilik komponentalarining diz’yunktiv birlashmasi
sifatida ifodalanishi mumkin, bunda grafning bog‘lamlilik komponentalariga
bo‘laklanishi bir qiymatli aniqlanadi.
Keyingi ma’lumotlarni bayon etish uchun yoq tushunchasi zarur bo‘ladi.
Tekislikda geometrik ifodalanuvchi grafni qaraymiz. Bu grafga tegishli bo‘lmagan
(ya’ni grafning hech qaysi uchi bilan ustma-ust tushmaydigan va uning hech qaysi](/data/documents/149bece6-5bcf-473f-815b-e3d80597b66a/page_20.png)
![qirrasida yotmaydigan) biror A nuqtani hech qaysi nuqtasi grafga tegishli bo‘lmagan
uzluksiz chiziq bilan tutashtirish mumkin bo‘lgan barcha nuqtalar to‘plami grafning
Yoq tushunchasiga berilgan ta’rifga ko‘ra yoq grafning geometrik ifodalanishi
yordamida tekislikning “qirqib” olinadigan qismidan iboratdir. Tekislikda geometrik
ifodalanuvchi ixtiyoriy grafning hech bo‘lmaganda bitta yoqi bo‘lishi va uning bitta
yoqi chegaraga ega emasligi (cheksizligi) o‘z-o‘zidan ravshandir.
Eyler teoremasidan bir qator natijalar kelib chiqadi. Masalan, bu teoremadan
foydalanib uni osonlik bilan bog‘lamli bo‘lmagan graflar uchun quyidagicha
umumlashtirish mumkin.
Tabiiyki, bog‘lamli grafdan qirrani yoki bir necha qirralarni olib tashlash
natijasida hosil bo‘lgan graf bog‘lamli bo‘lishi ham bo‘lmasligi ham mumkin. Agar
bog‘lamli grafdan qirrani olib tashlash amali grafning bog‘lamlilik xususiyatini
buzsa, u holda bunday qirrani ajratuvchi qirra debataymiz.
Ravshanki, berilgan bog‘lamli grafda ajratuvchi qirralar ko‘p bo‘lishlari
mumkin. Ajratuvchi qirralar to‘plamining hech qaysi qism to‘plami elementlari
ajratuvchi qirralar bo‘lmasa, bu qirralar to‘plamini kesim deb ataymiz. Grafdan
kesimga tegishli qirralar olib tashlansa, natijada ikki bog‘lamli komponentalari
bo‘lgan graf hosil bo‘lishi ravshandir. Agar kesim yagona qirradan iborat bo‘lsa, u
holda bu qirra ko‘prik deb ataladi.](/data/documents/149bece6-5bcf-473f-815b-e3d80597b66a/page_21.png)
![Xulosa
Xulosa qilib aytganda A lgoritm bilan ishlash barcha turdagi dasturlash
tillarida ishlash uchun kerak b o' ladi . Algoritmsiz biror bir dasturlash tilida
dastur yaratib bulmaydi . H ar bir dasturning dastlab algoritmini yaratib olish
zarur . A gar biz dasturimizning ketma - ketligini bilmasak , u dastur biz
uylagandan kuproq xajmni egallashi mumkin ekan . C ++ dasturlash tilida
malumotlarni izlash , saralash, qayta ishlash kabi amallarni yuqorida kursatib
utilganidagidek bir va ikki ulchovli massivlarda bajarilganini kurib bilim va
kunikmalarga ega bo’ldiz. C++ dasturi strukturasi xaqida, belgilar bayoni,
algoritm va dastur tushunchasi, malumotlarni kiritish va chiqarish
operatorlari xamda dasturda ishlatiladigan toifalar, ifodalar va kunikmalarini
ko’rib chiqdiz . Algoritmlash va dasturlash tillari buyicha yozilgan bir nechta
kitoblar bilan tanishib chiqdiz va ulardan kerakli malumotlarni oldiz .Bu
kurs ishida Graflarda eng qisqa masofani topish algoritmlarini bir nechtasini
ko’rib chiqdik asosan Floyd va Dijkstra algoritmlari haqida malumotlar
keltirildi.
Graflar elementlarni, odamlarni va ob’ektlarni bog’lash uchun
ishlatiladi va Dijkstra algoritmi grafdagi ikkita nuqta orasidagi eng qisqa
masofani aniqlashda sizga yordam beradi. Deykstra algoritmi haqiqiy
dunyoda juda muhim bo’lgani uchun uni to’g’ri o’rganish va tushunish
yaxshiroqdir.](/data/documents/149bece6-5bcf-473f-815b-e3d80597b66a/page_22.png)
![Foydalanilgan adabiyotlar
1. M.O‘. ASHUROV, SH.A.SATTAROVA, SH.U.USMONQULOV,
“ALGORITMLAR” , «Fan va texnologiya» nashriyoti, 2018.
2. H.To’rayev,“Kombinatorika va graflar nazariyasi”, “Ilm ziyo”, 2009 ,
3. Akbaraliyev B.B., Yusupova Z.Dj. , “MA LUMOTLAR TUZILMASI‟
VA ALGORITMLAR”, Toshkent 2013
4. Toirov Sh.A., Raximov R.T., Karimov M.M ,” “ALGORITMGA
KIRISH” fanidan laboratoriya ishlarini bajarish bo’yicha USLUBIY
KO’RSATMA”, Samarqand 2015.
5. Avnindra Kanaujia “Heap Sort Algorithms: Full Explanation of Heap
Sort Algorithm” November 17, 2017.
Foydalanilgan Internet saytlar
1. www.codingeek.com
2. www.geeksforgeeks.org
3. www.wikipedia.org
4. www.programiz.com
5. www.tutorialspoint.com
6. www.educba.com
7. www.btechsmartclass.com
8. www.commonlounge.com
9. www.brilliant.org
10. www.medium.com
11. www.researchgate.net
12. www.upgrad.com
13. www.quora.com](/data/documents/149bece6-5bcf-473f-815b-e3d80597b66a/page_23.png)
“GRAFLAR ENG QISQA MASOFA TOPISH ALGORITMLAR” mavzusida Mundarija Floyd Algoritmlari ........................................................................................................................................ 3 Haddan tashqari algoritmlar ........................................................................................................................ 5 Qaytish bilan qidirish. Ushbu usul chuqur qidirish uslubiga asoslangan. Qaytish bilan qidirish sinov va xato usuli hisoblanadi ("keling, bu yo'nalishda borishga harakat qilaylik – bu ishlamaydi - qaytib keling va boshqasiga harakat qilaylik"). Variantlarni qidirish chuqur qidirish usuli bilan amalga oshirilganligi sababli, algoritm ish paytida daraxtdagi joriy yo'lni saqlash tavsiya etiladi. Bu yo'l bir yo'l suyakka hisoblanadi.Bundan tashqari, bir qator Distga ehtiyoj bor, uning o'lchami grafikaning vertikalari soniga mos keladi, bu har bir Vertex uchun dastlabki tepadan masofani saqlaydi. ............................................ 5 To'lqin algoritmi. Kenglik qidiruviga asoslangan bu ortiqcha algoritm ikki bosqichdan iborat: to'lqin tarqalishi; teskari harakat. To'lqinning tarqalishi va hujayralar tashrif buyuradigan usulning qadam raqami bilan belgilanadigan kenglikdagi qidiruv mavjud. Qaytish jarayonida, oxirgi tepadan boshlab, minimal belgilar bilan hujayralarni kiritish yo'li bilan unga kiritilgan yo'lni tiklash (misol 45.4). Muhim xususiyat shundaki, tiklanish oxiridan boshlanadi (boshidan bu ko'pincha mumkin emas). .................... 6 Graflar ustida amallar ............................................................................................................................ 19 Xulosa ........................................................................................................................................................ 22 Foydalanilgan adabiyotlar ......................................................................................................................... 23 Foydalanilgan Internet saytlar ................................................................................................................... 23
Kirish Qandaydir masalani xal etishga kirishishdan avval buning uchun eng yaxshi uslub izlanadi va uni qay tarzda tavsiflash aniqlanadi. Boshqacha qilib aytganda, biz doimo maqsadi ba’zi bir zaruriy natijaga erishishdan iborat, amallar ketma-ketligi bilan berilgan turli-tuman qoidalarga duch kelamiz. Bunday amallarning ketma- ketligi algoritm deb ataymiz. Matematikada algoritmning murakkabligi, xal etish masalalari va ularni ishlab chiqish prinsiplarini o’rganadigan maxsus “Algoritmlar nazariyasi” bo’limi xam mavjud. Algoritmlar nazariyasi – algoritmlarning umumiy xossalari, qonuniyatlari va ularni tasvirlanishining turli-tuman formal modellarini o’rganish bilan shug’ullanadi. Algoritm tushunchasini formallashtirish asosida ularning samaradorligi taqqoslash, ularning ekvivalentligi tekshirish, qo’llanilish sohasini aniqlash mumkin. Graflar nazariysida eng qisqa yo’lni aniqlash muhim klassik masalalaridan biri deb hisoblanadi. Uni hisoblash va echimlarni topish uchun bir qancha algoritmlari mavjud. Eng qisqa yo’l masalasi (inglizchada – shortest path problem) – bu grafning ikkita tugun orasidagi eng qichik yo’l (masofa, zanjir, marshrut) topish masalasidir, qaysidaki yoylarning vaznlarining yig’indisi minimal qiymatga ega. Qisqa (oddiy) zanjir geodezik zanjir ham aytiladi. Ushbu masalani adabiyotlarda bir nechta boshqa nomlanishi ham uchratish mumkin: minimal masofa masalasi, dilijans masalasi, qisqa masofa masalasi va boshqalar. Grafda eng qisqa masofani topish masalasi yo’naltirilgan, yo’naltirilmagan va aralash graflarda echimini aniqlash mumkin.
Floyd Algoritmlari Ushbu algoritm ba'zan Floyd-Warshell algoritmi deb ataladi. Floyd-Warshell algoritmi 1962da Robert Floyd va Stiven Uorchell tomonidan ishlab chiqilgan graflarda algoritmdir. Grafning barcha juftlari orasidagi eng qisqa yo'llarni topishga xizmat qiladi. Floyd usuli to'g'ridan-to'g'ri qovurg'alarning ijobiy og'irliklari bo'lgan ustunda, har qanday elementar bo'lmagan (1 qovurg'asidan ko'prog'ini o'z ichiga olgan), eng qisqa yo'l boshqa eng qisqa yo'llardan iborat. Ushbu algoritm Dijkstra algoritmiga nisbatan ancha keng tarqalgan, chunki har qanday ikki ustun o'rtasida eng qisqa yo'llarnitopadi. Floyd algoritmida eng qisqa yo'llarning uzunligi hisoblangan NxN matritsasi ishlatiladi. A[i,j] elementi, agar u erda chekka (i, j) bo'lsa,yakuniy qiymatga ega bo'lgan va aks holda abadiylikka teng bo'lgan j ning yuqori qismidan masofaga teng. Floyd Algoritmning asosiy g'oyasi. I, j, k ning uchta tepasi bor va ular orasidagi masofa belgilanadi. Agar tengsizlik a[i,k]+a[k,j]<a[i,j] bajarilsa, i->j yo'lini i->k->j bilan almashtirish tavsiya etiladi. Qadam 0. A0 masofasining dastlabki matritsasini va S0 vertexlarining ketma-ketligini aniqlang. Har ikkala matritsaning har bir diagonali elementi 0ga teng, shuning uchun bu elementlarning hisob-kitoblarda ishtirok etmasligini ko'rsatmoqda. K = 1 ga ishonamiz. Asosiy qadam k. k satrini va k ustunini etakchi satr va etakchi ustun sifatida belgilang. Yuqorida tavsiflangan AK-1 matritsasining barcha elementlariga[i, j] almashtirishni ko'rib chiqamiz. Agar tengsizlik a[i,k]+a[k,j]<a[i,j], (i\ne k, j\ne k, i\ ne j) bajarilsa, unda quyidagi harakatlar amalga oshiriladi: A[i,k]+a[k,j] miqdori uchun A[i,j] elementining Ak-1 matritsasini almashtirish orqali Ak matritsasini yarating] ; k g6a SK-1 element s[i,j] matritsasini almashtirish orqali Sk matritsasini yarating. Shunday qilib, Floyd algoritmi n yinelemelerini qiladi, a matritsasining i- yinelemesinden keyin, bu yo'llar birinchi dan i-chigacha bo'lgan tepaliklardan o'tishi sharti bilan, har qanday ikki juftlik orasidagi eng qisqa yo'llarning uzunligini o'z ichiga oladi. Har bir iteratsiya bo'ylab barcha juftlar ko'chib o'tadi va ularning orasidagi yo'l i-tepa yordamida kamayadi.
Misol 45.2. Floyd algoritmini namoyish qilish // Floyd algoritm funktsiyasi tavsifi void Floyd(int n, int **Graph, int **ShortestPath) { int i, j, k; int Max_Sum = 0; for ( i = 0 ; i < n ; i++ ) for ( j = 0 ; j < n ; j++ ) Max_Sum+= ShortestPath[i][j]; for ( i = 0 ; i < n ; i++) if ( ShortestPath[i][j] == 0 && i!=j) ShortestPath[i][j] = Max_Sum; for ( k = 0 ; k <n;k++) for ( i = 0 ; i < n; i++) if ((ShortestPath[i][k] + ShortestPath[k][j]) ShortestPath[i][j] = ShortestPath[i][k] ; Agar grafik yo'naltirilmagan bo'lsa, unda transformatsiyalar natijasida olingan barcha matritsalar nosimmetrik bo'lib, shuning uchun faqat asosiy diagonaldan yuqorida joylashgan elementlarni hisoblash kifoya. Agar grafik qo'shni matritsasi bilan ifodalangan bo'lsa, unda bu algoritmning ishlash vaqti o(n3) buyrug'iga ega, chunki u bir-biriga biriktirilgan uchta tsiklni o'z ichiga oladi.
Haddan tashqari algoritmlar Bulkhead algoritmlari, odatda, optimal yechim topish uchun qidiruv algoritmlari. Shu bilan birga, yechim asta-sekin ishlab chiqilgan. Bunday holda, odatda, daraxt variantlarining ustunlarini qidirish haqida gap boradi. Bunday ustunning tepalari oraliq yoki yakuniy variantlar bo'ladi va qovurg'alar variantlarni loyihalash yo'llarini ko'rsatadi.Labirintdagi eng qisqa yo'lni topish vazifasi misolida ustundagi qidiruv usullariga asoslangan juda ko'p algoritmlarni ko'rib chiqing. Muammo bayonoti. O'tish va o'tkazilmaydigan hujayralardan tashkil topgan labirint mxn o'lchamli a matritsasi bilan berilgan. Agar hujayra (i,j) o'tkazilsa, matritsaning elementi a[i,j]=0. Aks holda, a [i,j]=\infty.Hujayradagi (1, 1) hujayradagi (m, n) eng qisqa yo'lning uzunligini topish kerak.Aslida, qo'shni matritsa berilgan (faqat nollar abadiylik bilan almashtiriladi va birliklar nolga teng). Labirint-bu grafik.Ushbu vazifadagi variantlar daraxtining tepalari qafada boshlangan yo'llardir (1, 1). Qovurg'alar-bu yo'llarning dizayni yo'lini ko'rsatadi va k va k+1 uzunliklarining ikki yo'lini birlashtiradi, bu erda ikkinchi yo'l yana bir harakatning yo'lini birinchi marta qo'shib olinadi. Qaytish bilan qidirish. Ushbu usul chuqur qidirish uslubiga asoslangan. Qaytish bilan qidirish sinov va xato usuli hisoblanadi ("keling, bu yo'nalishda borishga harakat qilaylik – bu ishlamaydi - qaytib keling va boshqasiga harakat qilaylik"). Variantlarni qidirish chuqur qidirish usuli bilan amalga oshirilganligi sababli, algoritm ish paytida daraxtdagi joriy yo'lni saqlash tavsiya etiladi. Bu yo'l bir yo'l suyakka hisoblanadi.Bundan tashqari, bir qator Distga ehtiyoj bor, uning o'lchami grafikaning vertikalari soniga mos keladi, bu har bir Vertex uchun dastlabki tepadan masofani saqlaydi.