6.2 TRAVEL DISTANCES ON NETWORKS

The most common question facing a motorist who sets out to drive from some location in a city to another concerns the choice of a route. Among the alternative routes available, one is chosen on the basis of such criteria as perceived travel distance, travel time, route "reliability," and so on. Similar choices must be made on a continuous basis by the dispatchers and/or the drivers of vehicles providing urban emergency services. The dispatchers, in particular, must mentally compare on a continuous basis the characteristics of alternative routes to an incident for a number of different, spatially distributed vehicles which are candidates for dispatching at any given time.

In this section we shall examine efficient methods for determining the paths that minimize travel time (or distance or cost) between any two specific points or between sets of pairs of points in a transportation network.

While the applicability of these techniques to the problem of vehicle dispatching and routing is obvious, there is an even more important motivation for beginning our presentation with a discussion of this topic: the determination of shortest paths appears consistently as a subproblem in virtually every network problem, and thus shortest-path algorithms are used as building blocks in algorithms that solve more complex problems.

A large number of algorithms have been proposed over the years for solving shortest-path problems. However, they can all be viewed as variations on a few basic themes and the two algorithms that will be described here illustrate all these themes. The first of the algorithms will determine the shortest paths between a given node and all other nodes in a network, while the second obtains simultaneously the shortest paths between all pairs of nodes. Both algorithms can be used with directed, undirected, or mixed graphs, and both assume that all link lengths are nonnegative. While this latter assumption is a reasonable one in the context of urban service systems--where link lengths usually represent travel distances or travel times-- this may not be the case in other applications where link lengths can, for instance, represent costs (and thus a negative link length would simply imply a "profit" for traversing the corresponding link).

Algorithms for determining shortest paths in networks with some negative link lengths also exist and can be viewed as relatively simple extensions of the two algorithms that will be described below especially with regard to Algorithm 6.2. Such algorithms are developed in Problem 6.1.