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?

In this chapter and in Chapter 26, we show how to solve such problems efficiently. In a * shortest-paths problem*, we are given a weighted, directed graph

We define the * shortest-path weight* from

if there is a path from *u* to *v*, otherwise.

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

The breadth-first-search algorithm from Section 23.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 23.2 before proceeding.

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

**Single-destination shortest-paths problem:** Find a shortest path to a given * destination* vertex

**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.* This problem can be solved by running a single-source algorithm once from each vertex; but it can usually be solved faster, and its structure is of interest in its own right. Chapter 26 addresses the all-pairs problem in detail.

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*)* * = -.

We often wish to compute not only shortest-path weights, but the vertices on the shortest paths as well. The representation we use for shortest paths is similar to the one we used for breadth-first trees in Section 23.2. Given a graph *G* = (*V, E*), we maintain for each vertex *v* *V* a **predecessor*** *[*v*] that is either another vertex or NIL. The shortest-paths algorithms in this chapter set the attributes so that the chain of predecessors originating at a vertex *v* runs backwards along a shortest path from *s* to *v*. Thus, given a vertex *v* for which [*v*] NIL, the procedure PRINT-PATH (*G*, *s, v*) from Section 23.2 can be used to print a shortest path from *s* to *v*.

During the execution of a shortest-paths algorithm, however, the * *values need not indicate shortest paths. As in breadth-first search, we shall be interested in the **predecessor subgraph***G** = (*V_{}, E_{}) induced by the values. Here again, we define the vertex set *V _{}*, to be the set of vertices of

V_{}_{ = {v V : [v] NIL} {s} .}

The directed edge set *E* is the set of edges induced by the values for vertices in *V** _{}*:

E_{}_{ = {([v], v) E : v V}_{}-{}}.

We shall prove that the values produced by the algorithms in this chapter have the property that at termination *G* is a "shortest-paths tree"--informally, a rooted tree containing a shortest path from a source *s* to every vertex that is reachable from *s*. A shortest-paths tree is like the breadth-first tree from Section 23.2, but it contains shortest paths from the source defined in terms of edge weights instead of numbers of edges. To be precise, let *G* = (*V, E*) be a weighted, directed graph with weight function *w* : *E* **R**, and assume that *G* contains no negative-weight cycles reachable from the source vertex *s* *V*, so that shortest paths are well defined. A * shortest-paths tree* rooted at

1. *V**'* is the set of vertices reachable from *s* in *G*,

2. *G**'* forms a rooted tree with root *s*, and

3. for all *v* *V**'*, the unique simple path from *s* to *v* in *G**'* is a shortest path from *s* to *v* in *G*.

Shortest-paths algorithms typically exploit the property that a shortest path between two vertices contains other shortest paths within it. This optimal-substructure property is a hallmark of the applicability of both dynamic programming (Chapter 16) and the greedy method (Chapter 17). In fact, Dijkstra's algorithm is a greedy algorithm, and the Floyd-Warshall algorithm, which finds shortest paths between all pairs of vertices (see Chapter 26), is a dynamic-programming algorithm. The following lemma and its corollary state the optimal-substructure property of shortest paths more precisely.

* Proof *By Lemma 25.1, subpath

(s,v) =w(p)

= w(p') + w(u, v)

= (s, u) + w(u, v).

The next lemma gives a simple but useful property of shortest-path weights.

The algorithms in this chapter use the technique of * relaxation*. For each vertex

INITIALIZE-SINGLE-SOURCE(G,s)

1foreach vertexvV[G]

2dod[v]

3 [v] NIL

4d[s] 0

After initialization, [*v*] = NIL for all *v* *V*, *d*[*v*] = 0 for *v* = *s*, and *d*[*v*] = for *v* *V* - {*s*}.

RELAX(u,v,w)

1ifd[v] >d[u] +w(u,v)

2thend[v]d[u] +w(u,v)

3 [v]u

d[u] +w(u,v) =d[v]

< (s,v)

(s,u) + w(u, v) (by Lemma 25.3),

* Proof *By Lemma 25.5, we always have =

d[v]d[u] +w(u,v) (by Lemma 25.4)

= (s,u) + w(u,v)

= (s,v) (by Corollary 25.2).

So far, we have shown that relaxation causes the shortest-path estimates to descend monotonically toward the actual shortest-path weights. We would also like to show that once a sequence of relaxations has computed the actual shortest-path weights, the predecessor subgraph *G* induced by the resulting values is a shortest-paths ree for *G *. __e __start with the following lemma, which shows that the predecessor subgraph always forms a rooted tree whose root is the source.

d[v]_{i}d[v1]+_{i - }w(v1,_{i -}_{ }v) for all_{i}i= 1, 2,...,k- 1 .

Because [*v _{k}*] is changed by the call, immediately beforehand we also have the strict inequality

d[vk] >d[v- 1] +_{k}w(v- 1,_{k}vk) .

since each vertex in the cycle *c* appears exactly once in each summation. This implies

The second property follows directly from Lemma 25.8.

= (s, v_{k}) - (s, v_{0)}

=_{}(_{s, v}k_{).}

Give two shortest-paths trees for the directed graph of Figure 25.2 other than the two shown.

Embellish the proof of Lemma 25.3 to handle cases in which shortest-path weights are or -.

Let *G* = (*V, E*) be a weighted, directed graph with no negative-weight edges. Let *s* *V* be the source vertex, and let us define [*v*] as usual: [*v*] is the predecessor of *v* on some shortest path to *v* from source *s* if *v* *V* - {*s*} is reachable from *s*, and NIL otherwise. Give an example of such a graph *G* and an assignment of values that produces a cycle in *G**.* (By Lemma 25.8, such an assignment cannot be produced by a sequence of relaxation steps.)

Dijkstra's algorithm solves the single-source shortest-paths problem on a weighted, directed graph *G* = (*V, E*) for the case in which all edge weights are nonnegative. In this section, therefore, we assume that *w*(*u, v*) 0 for each edge (*u, v*) *E*.

DIJKSTRA(G,w,s)

1 INITIALIZE-SINGLE-SOURCE (G,s)

2

3QV[G]

4while

5douEXTRACT-MIN(Q)

6SS{u}

7foreach vertexvAdj[u]

8doRELAX (u,v,w)

d[y] =(s,y)

(s,u)

d[u] (by Lemma 25.5).

d[y] =(s,y) =(s,u) =d[u] .

* Proof *Immediate from Theorem 25.10 and Lemma 25.9.

How fast is Dijkstra's algorithm? Consider first the case in which we maintain the priority queue *Q* = *V *- *S* as a linear array. For such an implementation, each EXTRACT-MIN operation takes time *O*(*V*), and there are |V*|* such operations, for a total EXTRACT-MIN time of *O*(*V*^{2})*. *Each* *vertex *v* *V* is inserted into set *S* exactly once, so each edge in the adjacency list *Adj*[*v*] is examined in the **for** loop of lines 4-8 exactly once during the course of the algorithm. Since the total number of edges in all the adjacency lists is |E*|*, there are a total of |E*|* iterations of this **for **loop, with each iteration taking *O*(1) time. The running time of the entire algorithm is thus *O*(*V*^{2} + *E*) = *O*(*V*^{2}).

If the graph is sparse, however, it is practical to implement the priority queue *Q* with a binary heap. The resulting algorithm is sometimes called the * modified Dijkstra algorithm*. Each EXTRACT-MIN operation then takes time

We can in fact achieve a running time of *O*(*V* lg *V *+ *E*) by implementing the priority queue *Q* with a Fibonacci heap (see Chapter 21). The amortized cost of each of the |V*|* EXTRACT-MIN operations is *O*(lg *V*), and each of the |E*|* DECREASE-KEY calls takes only *O*(1) amortized time. Historically, the development of Fibonacci heaps was motivated by the observation that in the modified Dijkstra algorithm there are potentially many more DECREASE-KEY calls than EXTRACT-MIN calls, so any method of reducing the amortized time of each DECREASE-KEY operation to *o*(lg *V*) without increasing the amortized time of EXTRACT-MIN would yield an asymptotically faster implementation.

Dijkstra's algorithm bears some similarity to both breadth-first search (see Section 23.2) and Prim's algorithm for computing minimum spanning trees (see Section 24.2). It is like breadth-first search in that set *S* corresponds to the set of black vertices in a breadth-first search; just as vertices in *S* have their final shortest-path weights, so black vertices in a breadth-first search have their correct breadth-first distances. Dijkstra's algorithm is like Prim's algorithm in that both algorithms use a priority queue to find the "lightest" vertex outside a given set (the set *S* in Dijkstra's algorithm and the tree being grown in Prim's algorithm), insert this vertex into the set, and adjust the weights of the remaining vertices outside the set accordingly.

Give a simple example of a directed graph with negative-weight edges for which Dijkstra's algorithm produces incorrect answers. Why doesn't the proof of Theorem 25.10 go through when negative-weight edges are allowed?

Suppose we change line 4 of Dijkstra's algorithm to the following.

4while|Q| > 1

Let *G* = (*V*, *E*) be a weighted, directed graph with weight function *w* : *E* {0, 1, . . . , *W* - 1} for some nonnegative integer *W*. Modify Dijkstra's algorithm to compute the shortest paths from a given source vertex *s* in *O*(*WV* + *E*) time.

The * Bellman-Ford algorithm* solves the single-source shortest-paths problem in the more general case in which edge weights can be negative. Given a weighted, directed graph

BELLMAN-FORD(G,w,s)

1 INITIALIZE-SINGLE-SOURCE(G,s)

2fori1to|V[G]| - 1

3do foreach edge (u,v)E[G]

4doRELAX(u,v,w)

5foreach edge (u,v)E[G]

6do ifd[v] >d[u] +w(u,v)

7then returnFALSE

8returnTRUE

* Proof *The proof is similar to that of Lemma 25.12 and is left as Exercise 25.3-2.

d[v] = (s,v)

(s,u) +w(u,v) (by Lemma 25.3)

=d[u] +w(u,v),

and so none of the tests in line 6 causes BELLMAN-FORD to return FALSE. It therefore returns TRUE.

Moreover, by Corollary 25.13, *d* [*v _{i}*] is finite for i = 1, 2, . . . ,

Suppose that a weighted, directed graph *G* = (*V, E*) has a negative-weight cycle. Give an efficient algorithm to list the vertices of one such cycle. Prove that your algorithm is correct.

By relaxing the edges of a weighted dag (directed acyclic graph) *G* = (*V, E*) according to a topological sort of its vertices, we can compute shortest paths from a single source in (*V* + *E*) time. Shortest paths are always well defined in a dag, since even if there are negative-weight edges, no negative-weight cycles can exist.

DAG-SHORTEST-PATHS(G,w,s)

1 topologically sort the vertices ofG

2 INITIALIZE-SINGLE-SOURCE(G,s)

3foreach vertexutaken in topologically sorted order

4do foreach vertexvAdj[u]

5doRELAX(u,v,w)

An example of the execution of this algorithm is shown in Figure 25.8.

An interesting application of this algorithm arises in determining critical paths in **PERT chart**^{2} analysis. Edges represent jobs to be performed, and edge weights represent the times required to perform particular jobs. If edge (*u*, *v*) enters vertex *v* and edge (*v*, *x*) leaves *v*, then job (*u*, *v*) must be performed prior to job (*v*, *x*). A path through this dag represents a sequence of jobs that must be performed in a particular order. A * critical path* is a

negating the edge weights and running DAG-SHORTEST-PATHS, or

^{2"}PERT" is an acronym for "program evaluation and review technique."

Run DAG-SHORTEST-PATHS on the directed graph of Figure 25.8, using vertex *r *as the source.

Suppose we change line 3 of DAG-SHORTEST-PATHS to read

3 **for** the first |*V*| - 1 vertices, taken in topologically sorted order

Show that the procedure would remain correct.

The PERT chart formulation given above is somewhat unnatural. It would be more natural for vertices to represent jobs and edges to represent sequencing constraints; that is, edge (*u, v*)* *would indicate that job *u* must be performed before job *v.* Weights would then be assigned to vertices, not edges. Modify the DAG-SHORTEST-PATHS procedure so that it finds a longest path in a directed acyclic graph with weighted vertices in linear time.

In the general linear-programming problem, we wish to optimize a linear function subject to a set of linear inequalities. In this section, we investigate a special case of linear programming that can be reduced to finding shortest paths from a single source. The single-source shortest-paths problem that results can then be solved using the Bellman-Ford algorithm, thereby also solving the linear-programming problem.

In the general * linear-programming problem*, we are given an

Many problems can be expressed as linear programs, and for this reason much work has gone into algorithms for linear programming. The **simplex algorithm**^{3} solves general linear programs very quickly in practice. With some carefully contrived inputs, however, the simplex method can require exponential time. General linear programs can be solved in polynomial time by either the * ellipsoid algorithm,* which runs slowly in practice, or

^{3 }The simplex algorithm finds an optimal solution to a linear programming problem by examining a sequence of points in the feasible region--the region in *n*-space that satisfies *Ax ** b. *The algorithm is based on the fact that a solution that maximizes the objective function over the feasible region occurs at some "extreme point," or "corner," of the feasible region. The simplex algorithm proceeds from corner to corner of the feasible region until no further improvement of the objective function is possible. A "simplex" is the convex hull (see Section 35.3) of *d* + 1 points in *d*-dimensional space (such as a triangle in the plane, or a tetrahedron in 3-space). According to Dantzig [53], it is possible to view the operation of moving from one corner to another as an operation on a simplex derived from a "dual" interpretation of the linear programming problem--hence the name "simplex method."

Sometimes we don't really care about the objective function; we just wish to find any * feasible solution*, that is, any vector

x_{j}- x_{i }b_{k ,}

For example, consider problem of finding the 5-vector *x* = (*x _{i}*) that satisfies

x_{1}-x_{2}0,

x_{1}-x_{5}-1,

x_{2}-x_{5}1,

x_{3}-x_{1}5,

x_{4}-x_{1}4,

x_{4}-x_{3 }-1,

x_{5}-x_{3 }-3,

x_{5}-x_{4}-3

It is beneficial to interpret systems of difference constraints from a graph-theoretic point of *v*iew. The idea is that in a system* Ax* *b* of difference constraints, the *n * *m* linear-programming matrix *A* can be *v*iewed as an incidence matrix (see Exercise 23.1-7) for a graph with *n* vertices and *m* edges. Each vertex *v _{i}* in the graph, for

V= {v_{0},v_{1}, . . . ,v}_{n}

E= {(v,_{i}v) :_{j}x-_{j}x_{i}bis a constraint}_{k}

{(v_{0},v_{1}),(v_{0},v_{2}),(v_{0},v_{3}),...,(v_{0},v)} ._{n}

Given a system *Ax* *b* of difference constraints, let *G* = (*V*, *E*) be the corresponding constraint graph. If *G* contains no negative-weight cycles, then

x = ((v_{0},v_{1}), (v_{0},v_{2}), (v_{0},v_{3}),..., (v_{0},v_{n}))

x_{2 }-x_{1}w(v_{1},v_{2}),

x_{3 }-x_{2}w(v_{2},v_{3}),

x-_{k }x_1_{k}w(v1,_{k-}v),_{k}

x_{1}-x_{k}w(v,_{k}v_{1}) .

Theorem 25.17 tells us that we can use the Bellman-Ford algorithm to solve a system of difference constraints. Because there are edges from the source vertex *v*_{0} to all other vertices in the constraint graph, any negative-weight cycle in the constraint graph is reachable from *v*_{0}. If the Bellman-Ford algorithm returns TRUE, then the shortest-path weights give a feasible solution to the system. In Figure 25.9, for example, the shortest-path weights provide the feasible solution *x *= (-5, -3, 0, -1, -4), and by Lemma 25.16, *x *= (*d* - 5, *d* - 3, *d*, *d* - 1, *d* - 4) is also a feasible solution for any constant *d*. If the Bellman-Ford algorithm returns FALSE, there is no feasible solution to the system of difference constraints.

x_{1 }-x_{2}1,

x_{1}-x_{4}-4,

x_{2}-x_{3}2,

x_{2}-x_{5}7,

x_{2 }-x_{6}5,

x_{3}-x_{6}10,

x_{4}-x_{2}2,

x_{5}-x_{1}-1,

x_{5}-x_{4}3,

x_{6}-x_{3}-8.

x1 -x2 4,

x1 -x5 5,

x2 -x4 -6,

x3 -x2 1,

x4 -x1 3,

x4 -x3 5,

x4 -x5 10,

x5 -x3 -4,

x5 -x4 -8.

Can any shortest-path weight from the new vertex *v*_{0} in a constraint graph be positive? Explain.

Express the single-pair shortest-path problem as a linear program.

Let *Ax* *b* be a system of *m* difference constraints in *n* unknowns. Show that the Bellman-Ford algorithm, when run on the corresponding constraint graph, maximizes subject to *Ax* *b* and *x _{i}* 0 for all

25-1 Yen's improvement to Bellman-Ford

Suppose that we order the edge relaxations in each pass of the Bellman-Ford algorithm as follows. Before the first pass, we assign an arbitrary linear order *v*_{1}, *v*_{2}, . . . , *v*|*V*_{|}, to the vertices of the input graph *G* = (*V*, *E*). Then, we partition the edge set *E* into *E*_{ E}*b*_{, where E}_{} = {(*v _{i}*,

**c.**** **How does this scheme affect the running time of the Bellman-Ford algorithm?

A *d*-dimensional box with dimensions (*x*_{1}, *x*_{2}, . . . , *x _{d}*)

* a. *Argue that the nesting relation is transitive.

* Arbitrage* is the use of discrepancies in currency exchange rates to transform one unit of a currency into more than one unit of the same currency. For example, suppose that 1 U.S. dollar buys 0.7 British pound, 1 British pound buys 9.5 French francs, and 1 French franc buys 0.16 U.S. dollar. Then, by converting currencies, a trader can start with 1 U.S. dollar and buy 0.7 9.5 0.16 = 1.064 U.S. dollars, thus turning a profit of 6.4 percent.

R[i_{1},i_{2}]R[i_{2},i_{3}]R[i1,_{k-}i]_{k}R[i,_{k}i_{1}] > 1.

Analyze the running time of your algorithm.

25-4 Gabow's scaling algorithm for single-source shortest paths

A * scaling* algorithm solves a problem by initially considering only the highest-order bit of each relevant input value (such as an edge weight). It then refines the initial solution by looking at the two highest-order bits. It progressively looks at more and more high-order bits, refining the solution each time, until all bits have been considered and the correct solution has been computed.

* b. *Show that we can compute

Let us now concentrate on computing _{i} from _{i - 1}.

2_{i - 1}(s,v)<_{i}(s,v)<2_{i - 1}(s,v) + |V| - 1

* d. *Define for

25-5 Karp's minimum mean-weight cycle algorithm

Let *G = (V, E)* be a directed graph with weight function *w: E * **R***,* and* *let* n* = |*V*|. We define the * mean weight* of a cycle

for all vertices *v ** V*. (*Hint:* Use both properties from part (a).)

* d. *Show that if *

* g. *Give an

Papadimitriou and Steiglitz [154] have a good discussion of the simplex method and the ellipsoid algorithm as well as other algorithms related to linear programming. The simplex algorithm for linear programming was invented by G. Danzig in 1947. Variants of simplex remain the most popular method for solving linear-programming problems. The ellipsoid algorithm is due to L. G. Khachian in 1979, based on earlier work by N. Z. Shor, D. B. Judin, and A. S. Nemirovskii. Karmarkar describes his algorithm in [115].