Mathematically, a road map can be viewed as a directed, weighted graph: a collection of intersections (the vertices) connected by roads (the arcs), which are a priori one-way and of varying lengths. The length of the arc from vertex u to vertex v is denoted by l (uv ).
A directed, weighted graph.
To get from a vertex u to a vertex v, we follow a path: a sequence of arcs that take us step by step towards our destination. The total length of the path is simply the sum of the lengths of all the arcs it traverses. For example, the path cba (the arc cb followed by the arc ba) has length 3 + 12 = 15. The path ed, consisting of a single arc, has length 9, the length of that arc.
A path may, of course, contain more arcs than another yet still be shorter. This is true of cbda, whose length, 3 + 2 + 1 = 6, is less than that of cba. There may also be no path between two vertices. In our example, in particular, it is impossible to get from b to e. By convention, the "shortest path" from b to e is said to be of infinite length.
