Desde el punto de vista matemático, un mapa de carreteras puede verse como un grafo dirigido y ponderado, es decir, un conjunto de cruces (los vértices) unidos por carreteras (los arcos) a priori de sentido único y longitudes variables. La longitud del arco que une el vértice u con el vértice v se denota por l (uv ).
Un grafo dirigido ponderado.
Para ir de un vértice u a un vértice v seguimos un camino, es decir, una sucesión de arcos que nos acerca paso a paso a nuestro objetivo. La longitud total del camino es simplemente la suma de las longitudes de cada uno de los arcos recorridos. Por ejemplo, el camino cba (el arco cb seguido del arco ba) tiene longitud 3 + 12 = 15. El camino ed, reducido a un único arco, tiene longitud 9, la longitud de ese arco.
Por supuesto, puede ocurrir que un camino pase por más arcos que otro y, sin embargo, tenga menor longitud. Así sucede con cbda, de longitud 3 + 2 + 1 = 6, menor que la de cba. Por último, también puede ocurrir que dos vértices no puedan unirse mediante un camino. En nuestro ejemplo, es imposible en particular ir de b a e. Por convenio, se dice que el «camino más corto» de b a e es de longitud infinita.
