Dal punto di vista matematico, una carta stradale può essere considerata un grafo orientato e pesato, cioè un insieme di incroci (i vertici) collegati da strade (gli archi) a priori a senso unico e di lunghezza variabile. La lunghezza dell’arco che collega il vertice u al vertice v si indica con l (uv ).
Un grafo orientato pesato.
Per andare da un vertice u a un vertice v si segue un cammino, cioè una successione di archi che ci conduce passo passo alla meta. La lunghezza complessiva del cammino è semplicemente la somma delle lunghezze di tutti gli archi percorsi. Per esempio, il cammino cba (l’arco cb seguito dall’arco ba) ha lunghezza 3 + 12 = 15. Il cammino ed, costituito da un solo arco, ha lunghezza 9, cioè la lunghezza di quell’arco.
Può naturalmente accadere che un cammino attraversi più archi di un altro pur avendo lunghezza minore. È il caso di cbda, lungo 3 + 2 + 1 = 6, inferiore a quella di cba. Può anche succedere che due vertici non possano essere collegati da un cammino. Nel nostro esempio, in particolare, è impossibile andare da b a e. Per convenzione, il «cammino più breve» da b a e si dice di lunghezza infinita.
