logo

GRAFLAR ENG QISQA MASOFA TOPISH ALGORITMLAR

Yuklangan vaqt:

12.08.2023

Ko'chirishlar soni:

0

Hajmi:

242.1513671875 KB
“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. 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). 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. 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. 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. 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. 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. 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 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. 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. 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 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; }
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;
    } }
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. 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 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 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. 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. 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

“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.