SKEDSOFT

Design Analysis Of Algorithm

Overview: A motorist wishes to find the shortest possible route from Chicago to Boston. Given a road map of the United States on which the distance between each pair of adjacent intersections is marked, how can we determine this shortest route?

One possible way is to enumerate all the routes from Chicago to Boston, add up the distances on each route, and select the shortest. It is easy to see, however, that even if we disallow routes that contain cycles, there are millions of possibilities, most of which are simply not worth considering. For example, a route from Chicago to Houston to Boston is obviously a poor choice, because Houston is about a thousand miles out of the way.

In this chapter and in All-Pairs Shortest Paths, we show how to solve such problems efficiently. In a shortest-paths problem, we are given a weighted, directed graph G = (V, E), with weight function w : E R mapping edges to real-valued-weights. The weight of path p = v0, v1, ..., vk is the sum of the weights of its constituent edges:

We define the shortest-path weight from u to v by

A shortest path from vertex u to vertex v is then defined as any path p with weight w(p) = δ(u, v).

In the Chicago-to-Boston example, we can model the road map as a graph: vertices represent intersections, edges represent road segments between intersections, and edge weights represent road distances. Our goal is to find a shortest path from a given intersection in Chicago (say, Clark St. and Addison Ave.) to a given inter-section in Boston (say, Brookline Ave. and Yawkey Way).

Edge weights can be interpreted as metrics other than distances. They are often used to represent time, cost, penalties, loss, or any other quantity that accumulates linearly along a path and that one wishes to minimize.

The breadth-first-search algorithm from Section 22.2 is a shortest-paths algorithm that works on unweighted graphs, that is, graphs in which each edge can be considered to have unit weight. Because many of the concepts from breadth-first search arise in the study of shortest paths in weighted graphs, the reader is encouraged to review Section 22.2 before proceeding.

Variants

In this chapter, we shall focus on the single-source shortest-paths problem: given a graph G = (V, E), we want to find a shortest path from a given source vertex s V to each vertex v V . Many other problems can be solved by the algorithm for the single-source problem, including the following variants.

  • Single-destination shortest-paths problem: Find a shortest path to a given destination vertex t from each vertex v. By reversing the direction of each edge in the graph, we can reduce this problem to a single-source problem.

  • Single-pair shortest-path problem: Find a shortest path from u to v for given vertices u and v. If we solve the single-source problem with source vertex u, we solve this problem also. Moreover, no algorithms for this problem are known that run asymptotically faster than the best single-source algorithms in the worst case.

  • All-pairs shortest-paths problem: Find a shortest path from u to v for every pair of vertices u and v. Although this problem can be solved by running a single-source algorithm once from each vertex, it can usually be solved faster. Additionally, its structure is of interest in its own right. All-Pairs Shortest Paths addresses the all-pairs problem in detail.

Optimal substructure of a shortest path

Shortest-paths algorithms typically rely on the property that a shortest path between two vertices contains other shortest paths within it. (The Edmonds-Karp maximum-flow algorithm in Maximum Flow also relies on this property.) This optimal-substructure property is a hallmark of the applicability of both dynamic programming and the greedy method. Dijkstra's algorithm, which we shall see in Dijkstra's algorithm, is a greedy algorithm, and the Floyd-Warshall algorithm, which finds shortest paths between all pairs of vertices, is a dynamic-programming algorithm. The following lemma states the optimal-substructure property of shortest paths more precisely.

Negative-weight edges

In some instances of the single-source shortest-paths problem, there may be edges whose weights are negative. If the graph G = (V, E) contains no negative-weight cycles reachable from the source s, then for all v V , the shortest-path weight δ(s, v) remains well defined, even if it has a negative value. If there is a negative-weight cycle reachable from s, however, shortest-path weights are not well defined. No path from s to a vertex on the cycle can be a shortest path-a lesser-weight path can always be found that follows the proposed "shortest" path and then traverses the negative-weight cycle. If there is a negative-weight cycle on some path from s to v, we define δ(s, v) = -.

Figure 24.1 illustrates the effect of negative weights and negative-weight cycles on shortest-path weights. Because there is only one path from s to a (the path s, a), δ(s, a) = w(s, a) = 3. Similarly, there is only one path from s to b, and so δ(s, b) = w(s, a) w(a, b) = 3 (-4) = -1. There are infinitely many paths from s to c: s, c, s, c, d, c, s, c, d, c, d, c, and so on. Because the cycle c, d, c has weight 6 (-3) = 3 > 0, the shortest path from s to c is s, c, with weight δ(s, c) = 5. Similarly, the shortest path from s to d is s, c, d, with weight δ(s, d) = w(s, c) w(c, d) = 11. Analogously, there are infinitely many paths from s to e: s, e, s, e, f, e, s, e, f, e, f, e, and so on. Since the cycle e, f, e has weight 3 (-6) = -3 < 0, however, there is no shortest path from s to e. By traversing the negative-weight cycle e, f, e arbitrarily many times, we can find paths from s to e with arbitrarily large negative weights, and so δ(s, e) = -. Similarly, δ(s, f) = -. Because g is reachable from f , we can also find paths with arbitrarily large negative weights from s to g, and δ(s, g) = -. Vertices h, i, and j also form a negative-weight cycle. They are not reachable from s, however, and so δ(s, h) = δ(s, i) = δ(s, j) = .