Singlesource Shortest Paths
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 AllPairs Shortest Paths, we show how to solve such problems efficiently. In a shortestpaths problem, we are given a weighted, directed graph G = (V, E), with weight function w : E → R mapping edges to realvaluedweights. The weight of path p = 〈v_{0}, v_{1}, ..., v_{k}〉 is the sum of the weights of its constituent edges:
We define the shortestpath 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 ChicagotoBoston 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 intersection 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 breadthfirstsearch algorithm from Section 22.2 is a shortestpaths 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 breadthfirst 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 singlesource shortestpaths 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 singlesource problem, including the following variants.

Singledestination shortestpaths 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 singlesource problem.

Singlepair shortestpath problem: Find a shortest path from u to v for given vertices u and v. If we solve the singlesource 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 singlesource algorithms in the worst case.

Allpairs shortestpaths 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 singlesource algorithm once from each vertex, it can usually be solved faster. Additionally, its structure is of interest in its own right. AllPairs Shortest Paths addresses the allpairs problem in detail.
Optimal substructure of a shortest path
Shortestpaths algorithms typically rely on the property that a shortest path between two vertices contains other shortest paths within it. (The EdmondsKarp maximumflow algorithm in Maximum Flow also relies on this property.) This optimalsubstructure 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 FloydWarshall algorithm, which finds shortest paths between all pairs of vertices, is a dynamicprogramming algorithm. The following lemma states the optimalsubstructure property of shortest paths more precisely.
Negativeweight edges
In some instances of the singlesource shortestpaths problem, there may be edges whose weights are negative. If the graph G = (V, E) contains no negativeweight cycles reachable from the source s, then for all v ∈ V , the shortestpath weight δ(s, v) remains well defined, even if it has a negative value. If there is a negativeweight cycle reachable from s, however, shortestpath weights are not well defined. No path from s to a vertex on the cycle can be a shortest patha lesserweight path can always be found that follows the proposed "shortest" path and then traverses the negativeweight cycle. If there is a negativeweight cycle on some path from s to v, we define δ(s, v) = ∞.
Figure 24.1 illustrates the effect of negative weights and negativeweight cycles on shortestpath 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 negativeweight 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 negativeweight cycle. They are not reachable from s, however, and so δ(s, h) = δ(s, i) = δ(s, j) = ∞.