1. To'plamlar, ularning berilish usullari va ular ustida amallar

Dastlabki qadam. Manbaga (1 belgili uchga) ₁  0
qiymatni mos qo‘yib,

bu uchni dastlab deb olamiz.
R  
deb qabul qilingan R to‘plamga kiritamiz:
R  {1} .
R  V \ R

Umumiy qadam. Boshlang‘ich uchi R to‘plamga, oxirgi uchi esa R

to‘plamga tegishli bo‘lgan barcha yoylar to‘plami

(R, R )
bo‘lsin. Har bir

(i, j) (R, R )
yoy uchun
h_ij  _i  c_ij
miqdorni aniqlaymiz, bu yerda  _i
deb
i  R

uchga mos qo‘yilgan qiymat (grafning 1 belgili uchidan chiqib i belgili uchigacha eng qisqa yo‘l uzunligi) belgilangan.

 _j 
min h_ij


(i, j ) ( R,R )
qiymatni aniqlaymiz.

(R, R )
to‘plamning oxirgi tenglikda

minimum qiymat beruvchi barcha elementlarini, ya’ni
(i, j)
yoylarni ajratamiz.

Ajratilgan yoylarning har biridagi
j  R
^{belgili uchga}  _j
qiymatni mos qo‘yamiz.

 _j ^{qiymat mos qo‘yilgan barcha j uchlarni R to‘plamdan chiqarib R to‘plamga}

kiritamiz.
Ikkala uchi ham R to‘plamga tegishli bo‘lgan barcha

(i, j)

yoylar uchun

_i  c_ij   _j ^{tengsizlikning bajarilishini tekshiramiz. Tekshirilayotgan tengsizlik}

j
^{o‘rinli bo‘lmagan (ja’ni} 

*
*
 _i  c_ij
bo‘lgan) barcha
j_* belgili uchlarning har biriga

*

j
^{mos qo‘yilgan eski} 
*
qiymat o‘rniga yangi
_i  c_ij
qiymatni mos qo‘yamiz va

⁴ Agar grafda umumiy uzunligi manfiy bo‘lgan sikl mavjud bo‘lsa, u holda grafning qandaydir s uchidan shu siklning biror i uchiga o‘tib, keyin esa, sikl bo‘ylab harakatlanib, i uchga istalgancha marta qaytish mumkin bo‘lganligidan, istalgancha kichik uzunlikka ega yo‘l tuzish mumkin.
⁵ Deykstra Edsger Vayb (Dijkstra Edsger Wybe, 1930-2002) – Gollandiya matematigi.

(i, j_* )
^{yoyni ajratamiz. Bunda eski} 

j
*
qiymat aniqlangan paytda ajratilgan yoyni

ajratilmagan deb hisoblaymiz.
Uchlarga qiymat mos qo‘yish jarayonini oxirgi ( k belgili) uchga qiymat mos qo‘yilguncha davom ettiramiz. Grafning 1 belgili uchidan (manbadan) chiqib

uning ixtiyoriy k uchigacha (oxirgi uchigacha) eng qisqa yo‘l uzunligi ^ _k
bo‘ladi.

Oxirgi qadam. Grafning oxirgi uchidan boshlab ajratilgan yoylar yo‘nalishiga qarama-qarshi yo‘nalishda uning 1 belgili uchiga kelguncha harakatlanib, natijada grafdagi 1 belgili uchdan ixtiyoriy k uchgacha eng qisqa uzunlikka ega yo‘l(lar)ni topamiz.

47. Ford algoritmi.

1-ta'rif. Quyidagi shartlarni qanoatlantiradigan ^{( f ,  )} juftlik S to`rdagi oqim deyiladi.

1.-to`rning barcha zvenolarini biror orientirlashti-rilishi;

2. ^{f (u)} - o`tkazuvchanlik qobiliyatidan katta bo`lmagan funktsiya. Shu bilan
birga barcha ichki uchlarda Kirxgof qonuni bajariladi, ya'ni uchga kiruvchi

barcha qirralar bo`yicha oqimlarning yig`indisi, undan chiquvchi qirralar bo`yicha oqimlarning yig`indisiga teng.
Boshqacha qilib aytganda:

1. 
   -to`rning barcha qirralari uchun;
   
2. 
   -barcha ichki uchlar uchun, bu yerda
   

Г ( ) ( Г ' ( ))  - orientirlashtirilishda uchdan chiquvchi -mos ravishda
ga kiruvchi) qirralar to`plami.
Ravshanki, to`rning barcha u chlari bo`yicha -qutblarni ham inobatga olgan taqdirda) larning yig`indisi nolga teng -chunki har bir qirra biror uchdan chiqib boshqasiga kiradi).
Qirralarning berilgan o`tkazuvchanlik qobiliyatlarida S to`rdan o`tuvchi maksimal oqimning miqdorini aniqlash masalasini ko`ramiz. Bu masalaning echimi to`rdagi kesimlar bilan bog`liqdir.
2-ta'rif. Agar to`rning ba'zi bir qirralarini olib tashlaganimizda, u bog`likli bo`lmay qutblari turli komponentlariga tushib qolsa, bu qirralar to`plami to`rning kesimi deyiladi.

3-shakl.
Yuqoridagi rasmda berilgan to`r uchun qirralar to`plamlari kesimlardir.

Agar kesimdan istalgan qirrasini olib tashlaganda kesim bo`lmay qolsa, u sodda deyiladi. masalan, kesimlar sodda, esa sodda emas.
Bog`likli to`rning sodda kesimi uni ikkita: qutbni o`zida saqlovchi chap va qutbni o`zida saqlovchi o`ng qismlarga ajratadi. Kesimning har bir qirrasi turli qismlarga tegishli bo`lgan uchlarni tutashtiradi. Agar kesimning qirrasi zveno bo`lsa, yoki chapdan o`ngga qarab yo`naltirilgan bo`lsa, u to`g`ri, aks holda teskari deyiladi.
3-ta'rif. Sodda kesimning o`tkazuvchanlik qobiliyati deb uning barcha to`g`ri qirralarining o`tkazuvchanlik qobiliyatlarining yig`indisiga aytiladi.
Masalan, kesimning o`tkazuvchanlik qobiliyati 5+1=6 teng, - kesimniki esa 3+2+3+2=10. Agar to`r bog`liqli bo`lmay qutblari turli komponentlariga tegishli bo`lsa, u holda yagona sodda kesim bo`sh to`plam, uning o`tkazuvchanlik qobiliyati esa nolga teng.