Considerăm un graf orientat G=(X,U) cu n noduri, în care fiecărui arc îi este asociat un număr întreg numit cost. Semnificaţia acestui cost poate fi foarte variată, în funcţie de domeniul pe care îl descrie graful. De exemplu, dacă graful reprezintă harta unui oraş în care arcele sunt străzile iar nodurile sunt intersecţiile dintre stăyi, atunci putem vorbi despre costul deplasării unui automobil între două intersecţii, de-a lungul unei străzi. Acesta s-ar putea măsura în cantitatea de benzină consumată, calculată prin prisma lungimii străzii în m sau in km.
Pentru evidenţierea costurilor tuturor arcelor unui graf cu n noduri se poate defini o matrice a, cu n linii *n coloane.există două forme ale acestei matrici:
Forma a): Fiecare element a[i,j] poate fi:
-c, dacă există un arc de cost c>0 între nodurile i şi j;
-0, dacă i=j;
-+¥, dacă nu există arc între nodurile i şi j.
Forma b): Este absolut similară, cu singura deosebire că în loc de +¥ avem -¥.
Forma a)se foloseşte pentru determinarea drumurilor de cost minim între două noduri, iar forma b) este utilizată în aflarea drumurilor de cost maxim.
Dacă dorim să citim matricea costurilor, evident că nu putem introduce de la tastatură “+¥”! În loc de “+¥” vom da un numar de la tastatură foarte mare.