De ce contează?
Deschizi atlasul rutier la pagina cu tabelul de distanțe dintre orașe. Pe linia
„Cluj” și coloana „Brașov” găsești un număr: câți kilometri sunt între ele pe
șoseaua directă. Pe diagonală, „Cluj”–„Cluj”, scrie 0. Iar pentru două
localități între care nu există drum direct, căsuța e goală — semn că trebuie
să treci prin altă parte. Matricea costurilor unui graf este exact acest tabel
de distanțe.
Ce este
Într-un graf neponderat ne interesa doar dacă există o muchie între două
noduri: matricea de adiacență ținea 1 sau 0. Dar într-un graf ponderat
fiecare muchie are un cost (kilometri, timp, preț). Acum nu mai vrem să știm
doar dacă sunt legate i și j, ci cât costă să mergi direct de la i
la j.
Matricea costurilor cost a unui graf ponderat cu n noduri se definește
prin trei reguli:
cost[i][j]= ponderea muchiei directe dintreișij, dacă ea există;cost[i][i] = 0— a rămâne pe loc nu costă nimic;- dacă nu există muchie directă
i–j, punem o valoare convențională „infinit” (notatăINF) — un număr foarte mare care înseamnă „inaccesibil direct”.
De ce „infinit”, și nu 0, pentru lipsa muchiei? Pentru că 0 are deja un
sens precis: cost zero, adică un drum gratis. Dacă ai marca absența muchiei
cu 0, un algoritm care caută drumul cel mai ieftin ar crede că poate sări
gratuit între orice două noduri — și ți-ar returna trasee inexistente.
Cei doi de „0” din acest tabel nu înseamnă același lucru — și aici pică
mulți. cost[i][i] = 0 spune „de la i la i ajungi gratis” (adevărat: stai
pe loc). Dar „nu există muchie i–j” NU înseamnă cost 0 — înseamnă că direct
nu se poate, oricâți bani ai avea. De aceea lipsa muchiei primește INF:
o valoare atât de mare încât niciun drum minim nu o va alege vreodată.