consideram un graf orientat gx,u cu in noduri, in care fiecarui arc i este asociat un numar ntreg numit cost. semnificatia acestui cost poate fi foarte variata, in functie de domeniul pe care l descrie graful. de exemplu, daca graful reprezinta harta unui oras in care arcele sunt strazile iar nodurile sunt intersectiile dintre stayi, atunci putem vorbi despre costul deplasarii unui automobil ntre doua intersectii, de-a lungul unei strazi. acesta s-ar putea masura in cantitatea de benzina consumata, calculata prin prisma lungimii strazii in m sau in km.



pentru evidentierea costurilor tuturor arcelor unui graf cu in noduri se poate defini o matrice a, cu in linii n coloane.exista doua forme ale acestei matrici
forma a fiecare element ai,j poate fi
-c, daca exista un arc de cost c0 ntre nodurile i si j
-0, daca ij
-, daca nu exista arc ntre nodurile i si j.
forma b este absolut similara, cu singura deosebire...