Consider a road map or public transport map. It can be described as a collection of route segments connecting points: each point is a junction, such as a crossroads or interchange. The travel time along each segment is not proportional to its length: it might be a motorway or a mountain track, and a journey may combine travel on foot, by train, by car and by metro…
Sometimes, then, we must first head east to catch a fast train that will take us farther west. On the map above, is the fastest route from A to B the red secondary road connecting them, or the motorway shown in blue?
Enumerating paths
------------------------
More generally, let us consider the possible paths between a starting point A and a destination B. One initial approach to finding a fast path is to enumerate every possible path starting at A. We can then identify those that lead to B and, among them, find a fastest one. To determine whether such an enumeration is feasible, we must ask how many different paths start at A (that is, paths differing by at least one segment). At least three segments meet at every point on the map. There are three possibilities at the starting point, followed by at least two possible segments at each subsequent point along a path. Thus, the number of paths passing through k points is at least 2 *k, and any one of them could potentially be the fastest route to destination B. Moreover, k is unknown. We must therefore explore paths with 2, 3, 4… stages. Although a path containing many points is rarely the fastest, this is not theoretically impossible: we must therefore enumerate every possible number of points from 1 to n – 2, where n* is the total number of points on the map. This exponential number of paths is therefore equal to:
