Previous Next |

## Shortest PathsEvery path in a weighted digraph has an associated path weight, the value of which is the sum of the weights of that path's edges. This essential measure allows us to formulate such problems as "find the lowest-weight path between two given vertices." These shortest-paths problems are the topic of this chapter. Not only are shortest-paths problems intuitive for many direct apps, but they also take us into a powerful and general realm where we seek efficient algorithms to solve general problems that can encompass a broad variety of specific apps. Several of the algorithms that we consider in this chapter relate directly to various algorithms that we examined in s 17 through 20. Our basic graph-search paradigm applies immediately, and several of the specific mechanisms that we used in s 17 and 19 to address connectivity in graphs and digraphs provide the basis for us to solve shortest-paths problems. For economy, we refer to weighted digraphs as networks. Screenshot shows a sample network, with standard representations. We have already developed an ADT interface with adjacency-matrix and adjacency-lists class implementations for networks in —we just pass ## Screenshot Sample network and representationsThis network (weighted digraph) is shown in four representations: list of edges, drawing, adjacency matrix, and adjacency lists (left to right). As we did for MST algorithms, we show the weights in matrix entries and in list nodes, but use edge references in our programs. While we often use edge weights that are proportional to their lengths in the drawing (as we did for MST algorithms), we do not insist on this rule because most shortest-paths algorithms handle arbitrary nonnegative weights (negative weights do present special challenges). The adjacency matrix is not symmetric, and the adjacency lists contain one node for each edge (as in unweighted digraphs). Nonexistent edges are represented by null references in the matrix (blank in the figure) and are not present at all in the lists. Self-loops of length As discussed at length in , we use references to abstract edges for weighted digraphs to broaden the applicability of our implementations. This approach has certain implications that are different for digraphs than the ones that we considered for undirected graphs in and are worth noting. First, since there is only one representation of each edge, we do not need to use the ## Screenshot Shortest-path treesA shortest-path tree (SPT) defines shortest paths from the root to other vertices (see Definition 21.2). In general, different paths may have the same length, so there may be multiple SPTs defining the shortest paths from a given vertex. In the example network shown at left, all shortest paths from The restriction in the definition to simple paths is unnecessary in networks that contain edges that have nonnegative weight, because any cycle in a path in such a network can be removed to give a path that is no longer (and is shorter unless the cycle comprises zero-weight edges). But when we consider networks with edges that could have negative weight, the need for the restriction to simple paths is readily apparent: Otherwise, the concept of a shortest path is meaningless if there is a cycle in the network that has negative weight. For example, suppose that the edge ## Screenshot All shortest pathsThis table gives all the shortest paths in the network of Screenshot and their lengths. This network is strongly connected, so there exist paths connecting each pair of vertices. The goal of a source-sink shortest-path algorithm is to compute one of the entries in this table; the goal of a single-source shortest-paths algorithm is to compute one of the rows in this table; and the goal of an all-pairs shortest-paths algorithm is to compute the whole table. Generally, we use more compact representations, which contain essentially the same information and allow clients to trace any path in time proportional to its number of edges (see Screenshot). In Java implementations, we build our algorithmic solutions to these problems into ADT implementations that allow us to build efficient client programs that can solve a variety of practical graph-processing problems. For example, as we see in , we implement solutions to the all-pairs shortest-paths classes as constructors within classes that support constant-time shortest-path queries. We also build classes to solve single-source problems so that clients who need to compute shortest paths from a specific vertex (or a small set of them) can avoid the expense of computing shortest paths for other vertices. Careful consideration of such issues and proper use of the algorithms that we examine can mean the difference between an efficient solution to a practical problem and a solution that is so costly that no client could afford to use it. Shortest-paths problems arise in various guises in numerous apps. Many of the apps appeal immediately to geometric intuition, but many others involve arbitrary cost structures. As we did with minimum spanning trees (MSTs) in , we sometimes take advantage of geometric intuition to help develop an understanding of algorithms that solve the problems but stay cognizant that our algorithms operate properly in more general settings. In , we do consider specialized algorithms for Euclidean networks. More important, in s 21.6 and 21.7, we see that the basic algorithms are effective for numerous apps where networks represent an abstract model of the computation. Road maps Tables that give distances between all pairs of major cities are a prominent feature of many road maps. We presume that the map maker took the trouble to be sure that the distances are the shortest ones, but our assumption is not necessarily always valid (see, for example, Exercise 21.11). Generally, such tables are for undirected graphs that we should treat as networks with edges in both directions corresponding to each road, though we might contemplate handling one-way streets for city maps and some similar apps. As we see in , it is not difficult to provide other useful information, such as a table that tells how to execute the shortest paths (see Screenshot). In modern apps, embedded systems provide this kind of capability in cars and transportation systems. Maps are Euclidean graphs; in , we examine shortest-paths algorithms that take into account the vertex position when they seek shortest paths. ## Screenshot Distances and pathsRoad maps typically contain distance tables like the one in the center for this tiny subset of French cities connected by highways as shown in the graph at the top. Though rarely found in maps, a table like the one at the bottom would also be useful, as it tells what signs to follow to execute the shortest path. For example, to decide how to get from Paris to Nice, we can check the table, which says to begin by following signs to Lyon. Airline routes Route maps and schedules for airlines or other transportation systems can be represented as networks for which various shortest-paths problems are of direct importance. For example, we might wish to minimize the time that it takes to fly between two cities or to minimize the cost of the trip. Costs in such networks might involve functions of time, of money, or of other complicated resources. For example, flights between two cities typically take more time in one direction than the other because of prevailing winds. Air travelers also know that the fare is not necessarily a simple function of the distance between the cities—situations where it is cheaper to use a circuitous route (or endure a stopover) than to take a direct flight are all too common. Such complications can be handled by the basic shortest-paths algorithms that we consider in this chapter; these algorithms are designed to handle any positive costs. The fundamental shortest-paths computations suggested by these apps only scratch the surface of the applicability of shortest-paths algorithms. In , we consider problems from apps areas that appear unrelated to these natural ones, in the context of a discussion of reduction, a formal mechanism for proving relationships among problems. We solve problems for these apps by transforming them into abstract shortest-paths problems that do not have the intuitive geometric feel of the problems just described. Indeed, some apps lead us to consider shortest-paths problems in networks with negative weights. Such problems can be far more difficult to solve than are problems where negative weights cannot occur. Shortest-paths problems for such apps not only bridge a gap between elementary algorithms and unsolved algorithmic challenges but also lead us to powerful and general problem-solving mechanisms. As with MST algorithms in , we often mix the weight, cost, and distance metaphors. Again, we normally exploit the natural appeal of geometric intuition even when working in more general settings with arbitrary edge weights; thus we refer to the "length" of paths and edges when we should say "weight" and to one path as "shorter" than another when we should say that it "has lower weight." We also might say that |

Previous Next |