8.3 How Are Shortest Paths Found?

When you leave your home to go to work, you probably have several different ways you can go. Some of them are pretty direct and some of them are more roundabout, but you have plenty of options available. If you want to take the “shortest” path from home to work, you’ll probably focus on some of the more direct routes and eliminate some of the longer or more circuitous routes. However, a shortest path can mean different things. For instance, driving through city streets may be the shortest physical driving distance (in terms of mileage), but if those streets have lots of stop lights and traffic congestion, then this “shortest path” could easily take longer in terms of the time spent driving than a longer distance on a highway that doesn’t have these impediments. If you want to minimize the time spent driving, the highway route will probably get you to work faster, but you’d actually be traveling a longer distance. Major city streets can take a long time to navigate at rush hour, but you’ll probably sail through them much quicker if you make the same journey late at night.

All of these things have to be considered when you’re figuring out the shortest path (or “best route”) to take when traveling from an origin to a destination. People have their own decision-making criteria and stick to their own rules when it comes to determining what they judge to be the shortest path from one place to another—things like “always keep to the main roads,” or “use highways whenever you can,” or “never make a left turn.” This is why vehicle navigation systems often offer multiple options, such as “shortest distance” or “shortest driving time,” and sometimes apply conditions like “avoid highways” to compute the best route between points.

Within a vehicle navigation system (or GIS), each line segment has a transit cost (or impedance) assigned to it. The transit cost reflects how many units (of things like distance or travel time) it takes to go the length of a particular edge. The transit cost may reflect the actual distance in miles from one junction to another along the edge. The transit cost could also be the equivalent time it takes to drive that particular segment. Whatever transit cost is used, that value will be utilized in the shortest path computation. Other impedance attributes can be modeled as well—segments could have different transit costs under certain conditions (such as heavy traffic or construction). These types of impedance factors can help in making a network more realistic for use.

The shortest path is then calculated using an algorithm, a step-by-step mathematical procedure designed to solve a particular kind of problem—in this case to determine the overall lowest transit cost to move along the network from a starting point to a destination. There are various types of shortest path algorithms, including Dijkstra’s Algorithm (see Hands-on Application 8.3: Solve Your Network Problems with Dijkstra for more information on how to use this algorithm), which will compute the path of lowest cost to travel from a starting point to any destination in the network. For instance, say you have three different destinations you plan to travel to (work, the pizza shop, and the grocery store). Dijkstra’s Algorithm will evaluate the overall transit cost from your home to each destination, and find the shortest path from your home to work, from your home to the pizza shop, and from your home to the grocery store.

Whatever type of algorithm is used, the system will compute the shortest path, given the constraints of the network (such as transit cost or directionality of things like one-way streets). The system can then generate directions for you by translating the selected path into the various turns and names of streets that you’ll take as you follow the path through to your destination. See Figure 8.7 for an example of using an online geospatial technology utility to compute the shortest path or best route between two locations. Also check out Hands-on Application 8.4: Online Mapping and Routing Applications and Shortest Paths for some other Web tools for online directions and routing.

Of course, sometimes you have more than one destination to visit—say you have three places you want to stop at (shoe store, music store, and bookstore) and you want to drive the overall shortest route to hit all three places. When you’re using geospatial technology to compute a shortest route between several of these stops, there are two types of scenario to choose from:

1. In the first scenario you need to find the shortest path when you’re going to be visiting stops in a pre-defined order: This means you have to stop at the shoe store first, the music store second, and the bookstore last. In this case, you’d want to find the shortest paths from your house to the shoe store, from the shoe store to the music store, and finally from the music store to the bookstore.
2. The second scenario involves finding the shortest path when you can arrange the order of visiting the stops: For instance, if the bookstore and the shoe store are near each other, it makes sense to rearrange your travels, so you visit them one after the other, and then drive to the music store.

Geospatial technology applications can help determine some solutions to both of these scenarios. To visit stops in a pre-determined order, the system will find the shortest route (of all possible routes) from the origin to the first stop, then choose the shortest route to travel from the first stop to the second stop, and so on. An example of this in vehicle navigation systems is being able to set up a “Via Point” (another stop) between your origin and final destination—the device will then calculate the route from the origin (or current location) to the Via Point, then from the Via Point to the final destination.

With the ability to rearrange the order of stops, a system will evaluate options by changing the order of visiting stops to produce the overall shortest route. See Figure 8.8 for an example of how the “shortest path” changes between visiting stops in order as opposed to being able to rearrange the order of visiting the stops. Additional constraints can be placed on the problem—for instance, you may have to return home (the starting point) after visiting all of the stops. In that scenario, when you rearrange the stops, the starting point also becomes the last stop, and this may affect how the reordering is done. Conversely, you may want to have your starting point and ending point different from one another, and these types of parameters will have to be placed on the problem. Keep in mind that if you can arrange the order of stops, the program will likely give a decent solution to the problem; however, the only way to truly identify which configuration is the best is for the program to work through every possible arrangement—something that would be impossible with a larger number of stops.