I study my Bible as I gather apples. First I shake the whole tree, that the ripest might fall. Then I climb the tree and shake each limb, and then each branch and then each twig, and then I look under each leaf.
attributed to Martin Luther c.
Life is an unfoldment, and the further we travel the more truth we can comprehend. To understand the things that are at our door is the best preparation for understanding those that lie beyond.
attributed to Hypatia of Alexandria c.by Elbert Hubbard in Little Journeys to the Homes of Great Teachers 8
Your mind will answer most questions if you learn to relax and wait for the answer. Like one of those thinking machines, you feed in your question, sit back, and wait . . .
William S. Burroughs, Naked LunchThe methods given in this paper require no foresight or ingenuity,
and hence deserve to be called algorithms.
Edward R. Moore, The Shortest Path Through a Maze
8
Shortest Paths
Suppose we are given a weighted directed graph GV, E, w with two special vertices, and we want to find the shortest path from a source vertex s to a target vertex t. That is, we want to find the directed path P starting at s and ending at t that minimizes the function X
wP :
For example, if I want to answer the question Whats the fastest way to drive from my old apartment in Champaign, Illinois to my wifes old apartment in Columbus, Ohio?, I might use a graph whose vertices are cities, edges are roads, weights are driving times, s is Champaign, and t is Columbus. The graph is directed, because driving times along the same road might be dierent
West on Church, north on Prospect, east on I, south on I, east on Airport Expressway, north on I, east on I, north on Grandview, east on th, north on Olentangy River, east on Dodridge, north on High, west on Kelso, south on Neil. Depending on trac. We live in Urbana now.
uv2P
wuv.
8. SP
in dierent directions. At one time, there was a speed trap on I just east of the IndianaOhio border, but only for eastbound trac.
8. Shortest Path Trees
Almost every algorithm known for computing shortest paths from one vertex to another actually solves large portions of the following more general single source shortest path or SSSP problem: Find shortest paths from the source vertex s to every other vertex in the graph. This problem is usually solved by finding a shortest path tree rooted at s that contains all the desired shortest paths.
Its not hard to see that if shortest paths are unique, then they form a tree, because any subpath of a shortest path is itself a shortest path. If there are multiple shortest paths to some vertices, we can always choose one shortest path to each vertex so that the union of the paths is a tree. If there are shortest paths from s to two vertices u and v that diverge, then meet, then diverge again, we can modify one of the paths without changing its length, so that the two paths only diverge once.
bcu sad
xyv
Figure 8.. If sabcdv solid and saxydu dashed are shortest paths, then sabcdu along the top is also a shortest path.
Although they are both optimal spanning trees, shortestpath trees and minimum spanning trees are very dierent creatures. Shortestpath trees are rooted and directed; minimum spanning trees are unrooted and undirected. Shortestpath trees are most naturally defined for directed graphs; minimum spanning trees are more naturally defined for undirected graphs. If edge weights are distinct, there is only one minimum spanning tree, but every source vertex induces a dierent shortestpath tree; moreover, it is possible for every shortest path tree to use a dierent set of edges from the minimum spanning tree.
TM8. Negative Edges
For most shortestpath problems, where the edge weights correspond to distance or length or time, it is natural to assume that all edge weights are nonnegative, or even positive. However, for many applications of shortestpath algorithms, it is natural to consider edges with negative weight. For example, the weight
TM8.. Negative Edges
85 85 10 10
23 23
18 16 18 16 12 30 12 30
14 14 426 426
Figure 8.. A minimum spanning tree and a shortest path tree of the same undirected graph.
of an edge might represent the cost of moving from one vertex to another, so negativeweight edges represent transitions with negative cost, or equivalently, transitions that earn a profit.
Negative edges are a thorn in the side of most shortestpath problems, because the presence of a negative cycle might imply that shortest paths may not be welldefiend. To be precise, a shortest path from s to t exists if and only if there is at least one path from s to t, but there is no path from s to t that touches a negative cycle. For any path from s to t that touches a negative cycle, there is a shorter path from s to t that goes around the cycle one more time. Thus, if at least one path from s to t touches a negative cycle, there is no shortest path from s to t.
2 8
s5 3t 41
Figure 8.. There is no shortest walk from s to t.
In part because we need to consider negative edge weights, this chapter explicitly considers only directed graphs. All of the algorithms described here also work for undirected graphs with essentially trivial modifications, if and only if negative edges are prohibited. Correctly handling negative edges in undirected graphs is considerably more subtle. We cannot simply replace every undirected edge with a pair of directed edges, because this would transform any negative edge into a short negative cycle. Subpaths of an undirected shortest path that contains a negative edge are not necessarily shortest paths; consequently, the set of all undirected shortest paths from a single source vertex may not define a tree, even if shortest paths are unique.
Technically, we should be discussing shortest walks here, rather than shortest paths, but the abuse of terminology is standard. If s can reach t, there must be a shortest simple path from s to t; its just NPhard to compute when there are negative cycles, by an easy reduction from the Hamiltonian path problem. On the other hand, if there is a shortest walk from s to t, that walk must be a simple path, and therefore must be the shortest simple path from s to t. Blerg.
8. SP
sss
111111 u 1 v u 1 v u 1 v
Figure 8.. An undirected graph where shortest paths from s are unique but do not dene a tree.
A complete treatment of undirected graphs with negative edges is beyond the scope of this book. I will only mention, for people who want to follow up via Google, that a single shortest path in an undirected graph with negative edges can be computed in OV EV 2 log Vtime, by a reduction to maximum weighted matching.
8. The Only SSSP Algorithm
Just like graph traversal and minimum spanning trees, many dierent SSSP algorithms can be described as special cases of a single generic algorithm, first proposed by Lester Ford inand independently described by George Dantzig inand again by George Minty in . Each vertex v in the graph stores two values, which inductively describe a tentative shortest path from s to v.
distv is the length of the tentative shortest sv path, or 1 if there is no such path.
predv is the predecessor of v in the tentative shortest sv path, or N if there is no such vertex.
The predecessor pointers automatically define a tentative shortestpath tree rooted at s; these pointers are exactly the same as the parent pointers in our generic graph traversal algorithm. At the beginning of the algorithm, we initialize the distances and predecessors as follows:
During the execution of the algorithm, an edge uv is tense if distuwuvdistv. If uv is tense, the tentative shortest path sv is clearly incorrect, because the path suv is shorter. We can correct or at least improve this obvious overestimate by relaxing the edge as follows:
Specifically, Dantzig showed that the shortest path problem can be phrased as a linear programming problem, and then described an interpretation of his simplex method in terms of the original graph. His description is morally equivalent to Fords relaxation strategy.
6
ISSSPs:
dists 0
preds N
for all vertices v 6 s
distv 1 predv N
8.. The Only SSSP Algorithm
Ruv:
distv distuwuv predv u
Now that everything is set up, Fords generic algorithm has a simple oneline description:
If FSSSP eventually terminates because there are no more tense edges, then the predecessor pointers correctly define a shortestpath tree, and each value distv is the actual shortestpath distance from s to v. In particular, if s cannot reach v, then distv1, and if any negative cycle is reachable from s, then the algorithm never terminates.
The correctness of Fords generic algorithm follows from the following series of simpler claims:
. At any moment during the execution of the algorithm, for every vertex v, the distance distv is either 1 or the length of a walk from s to v. This claim can be proved by induction on the number of relaxations.
. If the graph has no negative cycles, then distv is either 1 or the length of some simple path from s to v. Specifically, if distv is the length of a walk from s to v that contains a directed cycle, that cycle must have negative length. This claim implies that if G has no negative cycles, the relaxation algorithm eventually halts, because there are only a finite number of simple paths in G.
. If no edge in G is tense, then for every vertex v, the distance distv is the length of the predecessor path spredpredvpredvv. Specifically, if v violates this condition but its predecessor predv does not, the edge predvv is tense.
. If no edge in G is tense, then for every vertex v, the path of predecessor edges spredpredvpredvv is in fact a shortest path from s to v. Specifically, if v violates this condition but its predecessor u in some shortest path does not, the edge uv is tense. This claim also implies that if G has a negative cycle, then some edge is always tense, so the generic algorithm never halts.
So far I havent said anything about how to find tense edges, or which tense edges to relax if there is more than one. Just like whateverfirst search, there
Repeatedly relax tense edges, until there are no more tense edges.
FSSSPs:
ISSSPs
while there is at least one tense edge
R any tense edge
8. SP
are several dierent instantiations of Fords generic relaxation algorithm. Unlike whateverfirst search, however, the eciency and correctness of each search strategy depends on the structure of the input graph.
The rest of this chapter considers the four most common instantiations of Fords algorithm, each of which is the best choice for a dierent class of input graphs. Ill leave the remaining details of the generic correctness proof as exercises, and instead give more informative, selfcontained correctness proofs for each of these four specific algorithms.
8. Unweighted Graphs: BreadthFirst Search
In the simplest special case of the shortest path problem, all edges have weight 1, and the length of a path is just the number of edges. This special case can be solved by a species of our generic graphtraversal algorithm called breadthfirst search. Breadthfirst search is often attributed to Edward Moore, who described it inas Algorithm A as the first published method to find the shortest path through a maze. Especially in the context of VLSI wiring and robot path planning, breadthfirst search is sometimes attributed to Chin Yang Lee, who described several applications of Moores Algorithm A with proper credit to Moore in . However, in , more than a decade before Moore considered mazes, Konrad Zuse described an implementation of breadthfirst search, as a method to count and label the components of a disconnected graph.
Moore was motivated by a weakness in Claude Shannons mazesolving robot Theseus, which Shannon designed and constructed in . Theseus used a memoized version of depth first search, implemented using electromechanical relays; this was almost certainly the first implementation of depthfirst search in graphs. According to Moore, When this machine was used with a maze which had more than one solution, a visitor asked why it had not been built to always find the shortest path. Shannon and I each attempted to find economical methods of doing this by machine. He found several methods suitable for analog computation, and I obtained these algorithms.
Analog methods for computing shortest paths through mazes have been proposed using ball bearings, fluidplasma flow, chemical reaction waves, chemotaxis, resistor networks, electric circuits with LEDs, memristor networks, glow discharge in microfluidic chips, growing plants, slime mold, amoebas, ants, bees, nematodes, and tourists.
Konrad Zuse was one of the early pioneers of computing; he designed and built his first programmable computer later dubbed the Z in the late s from metal strips and rods in his parents living room; the Z and its original blueprints were destroyed by a British air raid in . ZusesPhD thesis describes the very first highlevel programming language, called Plankalkul. The first complete example of a Plankalkul program in Zuses thesis is an implementation of breadthfirst search to count components, along with a pseudocode explanation and an illustrated stepbystep trace of the algorithms execution on a disconnected graph with eight vertices. Due to the collapse of the Nazi government, Zuse was unable to submit his PhD thesis, and Plankalkul remained unpublished until . The first Plankalkul compiler was finally implemented inby Joachim Hohmann.
8
8.. Unweighted Graphs: BreadthFirst Search
Breadthfirst search maintains a firstinfirstout queue of vertices, which initially contains only the source vertex s. At each iteration, the algorithm Ps a vertex u from the front of the queue and examines each of its outgoing edges uv. Whenever the algorithm discovers an outgoing tense edge uv, it relaxes that edge and Pes vertex v onto the queue. The algorithm ends when the queue becomes empty.
BFSs: ISSSPs Ps
while the queue is not empty u P
for all edges uv
if distvdistu1
distv distu1 predv u Pv
hhif uv is tenseii hhrelax uvii
Breadthfirst search is somewhat easier to analyze if we break its execution into phases, by introducing an imaginary token. Before we P any vertices, we P the token into the queue. The current phase ends when we P the token out of the queue; we begin the next phase when we P the token into the queue again. Thus, the first phase consists entirely of scanning the source vertex s. The algorithm ends when the queue contains only the token. The modified algorithm is shown in Figure ., and Figure . shows an example of this algorithm in action. Let me emphasize that these modifications are merely a convenience for analysis; with or without the token, the algorithm Pes and Ps vertices in the same order, scans edges in the same order, and outputs exactly the same distances and predecessors.
BFSWTs:
ISSSPs
Ps
Phhstart the rst phaseii
while the queue contains at least one vertex u P
if u
else Phhstart the next phaseii
for all edges uv
if distvdistu1
distv distu1 predv u Pv
hhif uv is tenseii hhrelax uvii
Figure 8.. Breadthrst search with an endofphase token; bold red lines are only for analysis.
8. SP
hhh
s b d 112 bcbcbc
a da 1da2 1d
s0s0s0 hhh
44
e3 f2ge3 f2ge3 f2g
hf e 121212
bcbcbc
a2 1da2 1da2 1d
s0s0s0
Figure 8.6. A complete run of breadthrst search in a directed graph. Vertices are pulled from the queue in the order s b d c a g f e h, where is the endofphase token. Bold vertices are in the queue at the end of each phase. Bold edges describe the evolving shortest path tree.
Let me emphasize that in the following lemma, distv is just a variable maintained by the algorithm. While distv intuitively represents a tentative shortestpath distance, we cannot assume yet that distv is ever actually equal to the true shortestpath distance from s to v. Dont worry; well get there.
Lemma .. For every integer i0 and every vertex v, at the end of the ith phase, either distv1 or distvi, and v is in the queue if and only if distvi.
Proof: The proof proceeds by induction on i. The base case i0 is straight forward: At the start of the first phase at the end of the zeroth phase, the queue contains only the start vertex s and the token, and ISSSP just set dists 0 and distv 1 for all v 6 s.
So fix an integer i0. The inductive hypothesis implies that at the start of the ith phase, the queue contains every vertex u with distui1, followed by the token. In other words, the queue looks like this:
i1i1i1
Thus, before we P the token from the queue, ending the ith phase, we P every vertex u with distui1.
For each such vertex u, we consider every outgoing edge uv. If uv is tense, we set distv distu1, so that distvi, and then immediately
fff2
egegeg
333
8
ca g
P v into the queue. These are the only assignments to distance labels during the ith phase. Thus, by induction, during the entire ith phase, the queue contains some vertices with distance label i1, followed by the token, followed by some vertices with distance label i:
iii1i1
In particular, just before the ith phase ends, the queue contains the token,
followed by some vertices with distance label i. iii
Moreover, vertex v appears in this final queue if and only if distv was changed during the ith phase. Thus, at the end of the ith phase, the queue contains every vertex v with distvi. E
Lemma . implies that the main body of BFS assigns distance labels in non decreasing order; on the other hand, the distance label distv of each vertex v never increases. It follows that for each vertex v, the line distv distu1 is executed at most once, during phase distv. Similarly:
Each predecessor pointer predv is changed at most once, during phase distv.
Each vertex v is Ped into the queue at most once, during phase distv.
EachvertexuisPedfromthequeueatmostonce,duringphasedistu1.
For each edge uv, the comparison is distvdistu1 is performed at most once, during phase distu1.
Altogether, these observations imply that breadthfirst search runs in OVE time. Intuitively, we can think of the vertices in the queue as a wavefront expanding monotonically outward from the source vertex s, passing over each vertex and edge of the graph at most once. This expanding wavefront analogy was already proposed by Chin Yang Lee in , inspired by visualizations produced by his implementation of Moores Algorithm A.
These observations also imply that we can replace the condition if distvdistu1 by the arguably simpler test if distv1. Then distances play the same role as the marks maintained by other graphtraversal algorithms, which ensure that each vertex is visited only once. Specifically, a vertex is
marked if and only if its distance label is finite.
But we still need to prove that the final distance labels are correct!
Theorem .. When BFS ends, distv is the length of the shortest path in G from s to v, for every vertex v.
8.. Unweighted Graphs: BreadthFirst Search
8
8. SP
8
Proof: Fixanarbitraryvertexv,andconsideranarbitrarypathv0v1v in G, where v0s and vv. I claim that distvjj for each index j; in particular distv. We can prove this claim by induction on j as follows.
Trivially distv0dists0.
For any index j0, the induction hypothesis implies distvj1j1. Immediately after we P vertex vj1 from the queue, either distvjdistvj11 already, or we set distvj distvj11. In either case, we havedistvjdistvj11 j.
We just proved that distv is at most the length of an arbitrary path from s to v; it follows that distv is at most the length of the shortest path from s tov.
A similar induction proof implies that distv is the length of the predecessor path spredpredvpredvv, so this must be the shortest path. E
8. Directed Acyclic Graphs: DepthFirst Search
Shortest paths are also easy to compute in directed acyclic graphs, even when the edges are weighted, and in particular, even when some edges have negative weight. We dont have to worry about negative cycles, because by definition, dags dont have any cycles! Indeed, this is a completely standard dynamic programming algorithm.
Let G be a directed graph with weighted edges, and let s be the fixed start vertex. For any vertex v, let distv denote the length of the shortest path in G from s to v. This function satisfies the following simple recurrence:
distv0 if vs min distuwuv otherwise
In fact, this identity holds for all directed graphs, but it is only a recurrence for directed acyclic graphs. If the input graph G contained a cycle, a recursive evaluation of this function would fall into an infinite loop; however, because G is a dag, each recursive call visits an earlier vertex in topological order.
The dependency graph for this recurrence is the reversal of the input graph G: subproblem distv depends on distu if and only if uv is an edge in G. Thus, we compute the distance of every in OVE time by performing a depthfirst search in the reversal of G and considering vertices in postorder. Equivalently, we can consider the vertices in the original graph G in topological order, as shown in Figure ..
The resulting dynamicprogramming algorithm is another example of Fords generic relaxation algorithm! To make this connection clearer, we can move the initialization distv outside the main loop and add computation of predecessor pointers, as shown in Figure .. Figure . shows this algorithm in action.
uv
DSSSPs:
for all vertices v in topological order
if vs
distv 0 else
distv 1
for all edges uv
if distvdistuwuv hhif uv is tenseii distv distuwuv hhrelax uvii
Figure 8.. Computing shortest paths in a dag using dynamic programming DSSSPs:
ISSSPs
for all vertices v in topological order for all edges uv
if uv is tense Ruv
Figure 8.8. Computing shortest paths in a dag using Fords algorithm. These are the same algorithm.
8.. Directed Acyclic Graphs: DepthFirst Search
7 12 0
0 362 11
7 12 0
0 362 11
8 5 10 3
7 12 0
0 3 3 62 11
8 5 10 3
7 12 0
0 3 3 6 8 2 6 13 11
8 5 10 3
7 12 0
03 36 82 6 131 81
8 5 10 3
0 3
0 3
03
8 5 10 3
7 12 0
3 6 8 2 118 5 10 3
7 12 0
3 6 8 2 6118 5 10 3
7 12 0
36 82 6 131 81 9 8 5 10 3
Figure 8.. Computing shortest paths in a dag, by relaxing incoming edges in topological order. In each iteration, bold edges indicate predecessors, and the bold vertex is about to be scanned. Compare with Figure 8..
.
8
8. SP
DSSSP diers from breadthfirst search and other instances of Fords relaxation strategy in one minor respect. Whenever these other shortestpath algorithms consider a vertex, they attempt to relax each of its outgoing edges, intuitively pushing the wavefront forward from the source; whereas, DSSSP attempts to relax each of the incoming edges of each vertex, intuitively pulling the wavefront forward.
However, if we modify DSSSP to relax outgoing edges instead of incoming edges, we obtain another algorithm that computes shortest paths in dags in OVE time and that more closely resembles our other shortestpath algorithms.
PDSSSPs: ISSSPs
for all vertices u in topological order for all outgoing edges uv
if uv is tense Ruv
Figure . shows an execution of this modified algorithm on the same graph as Figure .. The correctness of PDSSSP follows immediately from the correctness of Fords general relaxation strategy, but its not hard to prove correctness directly, by induction over the vertices in topological order.
8.6 BestFirst: Dijkstras Algorithm
If we replace the FIFO queue in breadthfirst search with a priority queue, where the key of a vertex v is its tentative distance distv, we obtain an algorithm first published inby a team of researchers at the Case Institute of Technology led by Michael Leyzorek, in an annual project report for the Combat Development Department of the US Army Electronic Proving Ground. The same algorithm was independently discovered by Edsger Dijkstra inbut not published until , again by George Minty some time before , and again by Peter Whiting and John Hillier in . A nearly identical algorithm was also described by George Dantzig in . Although several early sources called it Mintys algorithm, this approach is now universally known as Dijkstras algorithm,infullaccordancewithStiglersLaw. Pseudocodeforthisalgorithm is shown in Figure ..
An easy induction proof implies that, at all times during the execution of this algorithm, an edge uv is tense if and only if vertex u is either in the priority
I will follow this common convention, despite the historical inaccuracy, partly because I dont think anybody wants to read about the LeyzorekGrayJohnsonLadewMeakerPetrySeitz DantzigDijkstraMintyWhitingHillier algorithm, and partly because papers that arent actually published dont count.
8
7 12 0 7 12 0 0 362 110 3 3 6 8 2 7
8.6. BestFirst: Dijkstras Algorithm
115103
85103 8
7 12 0 7 12 0
15 115 10 3
851038
851038
0 3
0 3
03
3 6 8 2 6 13 1 8 10 3 3 6 8 2 7 851038
7 12 0 7 12 0 3 6 8 2 6 13 1 8 10 3 3 6 8 2 6
13 1 8 1 10 5103
7 12 0 7 12 0 36 82 6 131 81 9 03 36 82 6
131 81 9 5103
Figure 8.. Computing shortest paths in a dag, by relaxing outgoing edges in topological order. In each iteration, bold edges indicate predecessors, and the bold vertex is about to be scanned. Compare with Figure 8..
Ds: ISSSPs Is, 0
while the priority queue is not empty u EM
for all edges uv
if uv is tense Ruv
if v is in the priority queue
DKv, distv
else
Iv, distv
Figure 8.. Dijkstras algorithm.
8
8. SP
queue or is the vertex most recently Eed from the priority queue. Thus, Dijkstras algorithm is an instance of Fords general strategy, which implies that it correctly computes shortest paths, provided there are no negative cycles in G.
No Negative Edges
Dijkstras algorithm is particularly wellbehaved when the input graph has no negativeweight edges. In this setting, the algorithm intuitively expands a wavefront outward from the source vertex s, passing over vertices in increasing order of their distance from s, similarly to breadthfirst search. Figure . shows the algorithm in action.
323232
1 1 1 15
050505
1012 10 4 12 10 4 12 878787
44343 434343
000 7
32 32 419419
05 05
10 4 12 10 4 12 87 87
14 4 34 3 43 43
00
Figure 8.. The rst four iterations of Dijkstras algorithm on a graph with no negative edges. In each iteration, bold edges indicate predecessors; shaded vertices are in the priority queue; and the bold vertex is about to be scanned. The remaining iterations do not change the distances or the shortestpath tree.
We can derive a selfcontained proof of correctness for Dijkstras algorithm in this setting by formalizing this wavefront intuition. For each integer i, let ui denote the vertex returned by the ith call to EM, and let di be the value of distui just after this Eion. In particular, we have u1s and d10. We cannot assume at this point that the vertices ui are distinct; in principle, the same vertex might be Eed more than once.
Lemma .. If G has no negativeweight edges, then for all ij, we have di dj.
Proof: Assume G has no negative weight edges. Fix an arbitrary index i; to prove the lemma, it suces to prove that di1di. There are two cases to consider.
86
If G contains the edge uiui1, and this edge is relaxed during the ith iteration of the main loop, then at the end of the ith iteration, we have distui1distuiwuiui1distui, because all edge weights are nonnegative.
Otherwise, at the start of the ith iteration, ui1 must already be in the priority queue, and it must have priority distui1distui, because ui is the vertex returned by EM. Moreover, distui1 does not change during the ith iteration.
In both cases, we conclude that di1di. The lemma now follows immediately by induction on i. E
Lemma .. If G has no negativeweight edges, each vertex of G is Eed from the priority queue at most once.
Proof: Suppose v is Eed more than once. Specifically, suppose v is Eed in the ith iteration of the main loop, reIed during the jth iteration, and reEed during the kth iteration, for some indices ijk. Then in the notation of the previous proof, we have vuiuk.
The distance label distv never increases. Moreover, distv strictly decreases during the jth iteration, just before v is reIed. It follows that didk. Therefore, by the previous lemma, G has at least one negativeweight edge. E
Lemma . immediately implies that each vertex is scanned at most once, and thus that each edge is relaxed at most once. However, unlike in breadthfirst search, each distance label distv can change multiple times. The first time distv changes from 1, we I v into the priority queue; after that, each change to distv is followed by a call to DK. After v is Eed from the priority queue, its distance label never changes.
The rest of the correctness proof is almost identical to breadthfirst search.
Theorem .. If G has no negativeweight edges, then when D ends, distv is the length of the shortest path in G from s to v, for every vertex v.
Proof: Fixanarbitraryvertexv,andconsideranarbitrarypathv0v1v inG,wherev0sandvv.Foranyindexj,letLj denotethelengthofthe subpath v0v1vj. We prove by induction that distvjLj for all j.
Trivially distv0dists0L0.
For any index j0, the induction hypothesis implies distvj1Lj1. Immediately after we P vertex vj1 from the queue, either distvidistvj1wvj1vjalready,orwesetdistvi distvj1wvj1vj. In either case, we have
distvjdistvj1wvj1vjLj1wvj1vjLj.
8
8.6. BestFirst: Dijkstras Algorithm
8. SP
We just proved that distv is at most the length of every path from s to v; it follows that distv is at most the length of the shortest path from s to v.
On the other hand, a similar induction proof implies that distv is the length of the predecessor path spredpredvpredvv. E
It remains only to bound the algorithms running time. Altogether D performs at most E DK operations, and at most V I and EM operations. Thus, if we implement the underlying priority queue using a standard binary heap, which supports each operation in Olog Vtime, D runs in OE log V time.
If we know in advance that our input graphs will never have negative edges, we can simplify Dijkstras algorithm slightly, by Iing every vertex into the priority queue in the initialization phase, and then only calling DK in the main loop, as shown in Figure .. This is the version of Dijkstras algorithm presented by most algorithms textbooks, Wikipedia, and even Dijkstras original paper; its also the version of Dijkstras algorithm that I described as bestfirst search in Chapter .
NDs: ISSSPs
for all vertices v
Iv,distv
while the priority queue is not empty u EM
for all edges uv
if uv is tense Ruv
DKv,distv
Figure 8.. Dijkstras algorithm very slightly simplied for graphs without negative edges. Differences
from D are bold red. TMNegative Edges
However, ND does not correctly compute shortest paths in graphs with negative edges. Moreover, even when all edge weights are
Shortestpath papers from the s never mentioned priority queues. Dijkstra proposed a bruteforce scan of all vertices on the wavefront at every iteration; his original algorithm runs in OV2 time, which is actually faster than the binaryheap implementation when EV2! Minty proposed a bruteforce scan of all edges uv such that distu is finite but distv is not; thus, his original algorithm runs in OV E time. The use of a priority queue, implemented as a binary heap, to obtain nearlinear running time was proposed by Donald Johnson in . The running time can be improved to OEV log V using a more complex priority queue data structure called a Fibonacci heaps. There are even faster algorithms, using even more sophisticated priority queues, for the special case of integer edge weights.
88
8.. Relax ALL the Edges: BellmanFord
positive, ND is no faster than D either in theory or in practice. For both of these reasons, I think D is more deserving of the name Dijkstras algorithm than ND. Even Edsger Dijkstra would have agreed that a correct algorithm that is sometimes and in practice, rarely slow is better than a fast algorithm that doesnt always work!
Unfortunately, when the input graph has negative edges, the familiar expanding wavefront intuition is no longer accurate. The same vertex can be Eed multiple times; the same edge can be relaxed multiple times; and distances might not be discovered in increasing order. Figure . shows an example execution where the top left vertex is E six times, and the
top three edges are each relaxed twice.
For graphs without negative cycles, but no other restrictions on edge weights,
the worstcase running time of D is actually exponential. Figure . shows particularly simple family of graphs due to Douglas Shier and Christoph WitzgallthatforcesDtoperform2V2relaxations. Amorecomplex family of graphs which Ill leave as an exercise forces 2Vrelaxations, which is the worst possible. In practice, however, Dijkstras algorithm is usually fast even for graphs with negative edges.
0 2k 0
16 0
8 0
4 0 2 1
8
8. Relax ALL the Edges: BellmanFord
The simplest implementation of Fords generic shortestpath algorithm was first sketched by Alfonso Shimbel in , described in more detail by Edward Moore in , and independently rediscovered by Max Woodbury and George Dantzig in , by Richard Bellman in , and by George Minty in . Neither Woodbury and Dantzig nor Minty published their algorithms. In full compliance with Stiglers Law, the algorithm is almost universally known as BellmanFord, because Bellman explicitly used Fordsformulation of
Amusingly, Shier and Witzgalls example is a dag with only OV edges, which implies that shortest paths can be computed in only OV time, even if we didnt already notice that the zigzag path along the top is the shortest path tree.
I will follow this common convention, despite the historical inaccuracy, partly because I dont think anyone really wants read about the ShimbelMooreWoodburyDantzigBellman FordKalabaMinty algorithm, and partly because Im tired of people looking at me funny when I talk about Shimbels algorithm.
4
2
2k1
Figure 8.. A directed graph with negative edges that forces D to run in exponential time.
8
8. SP
5 1 5 1 5 1
3 35 3
7 5 7 5 7 5
23 2 10 3 2 9 3 686868
103 10 4 3 10 4 343434
000 8
5 1 5 1 5 1
4 3 7 5 3 7 5 3 7
7 5 7 5 7 5 293293293 686868
3 10 4 3 10 4 3 10 4 343434
000 888
5 1 5 1 5 1
4 3 7 3 3 7 3 3 7
7 5 7 5 7 5 293293293 686868
3 10 4 3 10 4 3 10 4 343434
000 588
5 1 5 1 5 1
1 3 4 2 3 4 2 3 4
7 5 7 5 7 5 293293293 686868
3 10 4 3 10 4 3 10 4 343434
000 555
5 1 5 1 5 1
1 3 4 0 3 4 0 3 4
7 5 7 5 7 5 293293293 686868
3 10 4 3 10 4 3 10 4 343434
000
Figure 8.. A complete run of Dijkstras algorithm on a graph with negative edges. At each iteration, bold edges indicate predecessors; shaded vertices are in the priority queue; and the bold vertex is the next to be scanned. Compare with Figure 8..
8.. Relax ALL the Edges: BellmanFord
relaxing edges, although some authors refer to BellmanKalaba and a few early sources refer to BellmanShimbel.
The ShimbelMooreWoodburyDantzigBellmanFordKalabaMintyBrosh algorithm can be summarized in one line:
BFs ISSSPs
while there is at least one tense edge for every edge uv
if uv is tense Ruv
The following lemma is the key to proving both correctness and eciency of BellmanFord. For every vertex v and nonnegative integer i, let distiv denote the length of the shortest walk in G from s to v consisting of at most i edges. In particular, dist0s0 and dist0v1 for all v 6 s.
Lemma .. For every vertex v and nonnegative integer i, after i iterations of the main loop of BF, we have distvdistiv.
Proof: The proof proceeds by induction on i. The base case i0 is trivial, so assume i0. Fix a vertex v, and let W be the shortest walk from s to v consisting of at most i edges breaking ties arbitrarily. By definition, W has length distiv. There are two cases to consider.
Suppose W has no edges. Then W must be the trivial walk from s to s, so vs and distis0. We set dists 0 in ISSSP, and dists can never increase, so we always have dists0.
Otherwise, let uv be the last edge of W. The induction hypothesis implies that after i1 iterations, distudisti1u. During the ith iteration of the outer loop, when we consider the edge uv in the inner loop, either distvdistuwuv already, or we set distv distuwuv. Inbothcases,wehavedistvdisti1uwuvdistiv. Asusual, distv cannot increase although distv might decrease further before the ith iteration of the outer loop ends.
This name is most likely a reference to Richard Bellman and Robert Kalabasmonograph on dynamic programming and control theory, which describes Bellmans algorithm. Bellman and Kalaba also published an extension of Bellmans algorithm inthat computes kth shortest paths, for any constant k.
Go read everything in Hyperbole and a Half again. And then adopt another cat, so you can buy it another copy of the book.
BF: Relax ALL the tense edges, then recurse.
8. SP
In both cases, we conclude that distvdistiv at the end of the ith iteration. E
If the input graph has no negative cycles, the shortest walk from s to any other vertex is a simple path with at most V1 edges; it follows that B F halts with the correct shortestpath distances after at most V1 iterations. Said dierently, if any edge is still tense after V1 iterations, then the input graph must contain a negative cycle! Thus, we can rewrite the algorithm more concretely as follows:
BFs ISSSPs
repeat V1 times
for every edge uv
if uv is tense Ruv
for every edge uv if uv is tense
return Negative cycle!
Each iteration of the inner loop trivially requires OE time, so the overall algorithm runs in OVE time. Thus, BellmanFord is always ecient, even if the graph has negative edges, and in fact even if the graph has negative cycles.
If all edge weights are nonnegative, however, Dijkstras algorithm is faster, at least in the worst case. In practice, Dijkstras algorithm is often faster than BellmanFord even for graphs with negative edges.
Moores Improvement
Neither Moore nor Bellman described the BellmanFord algorithm in the form Ive presented here. Moore presented his version of the algorithm Algorithm D in the same paper that proposed breadthfirst search Algorithm A for unweighted graphs; indeed, the two algorithms are nearly identical. Although Moores algorithm has the same OV E worstcase running time as BF, it is often significantly faster in practice, intuitively because it avoids checking edges that are obviously not tense.
Moore derived his weighted shortestpath algorithm by making two modifi cations to breadthfirst search. First, replace each 1 with wuv in the innermost loop, to take the edge weights into account. Second, check whether a vertex is already in the FIFO queue before Iing it, so that the queue always contains at most one copy of each vertex.
Moores algorithm is still correct without this check, but the OV E time bound is not.
8.. Relax ALL the Edges: BellmanFord
Following our earlier analysis of breadthfirst search, Ill introduce a token to break the execution of the algorithm into phases. Just like breadthfirst search, each phase begins when the token is Ped into the queue, and ends when the token is Ped out of the queue again. Just like BFS, the algorithm ends when the queue contains only the token. The resulting algorithm is shown in Figure ..
Ms:
ISSSPs
Ps
Phhstart the rst phaseii
while the queue contains at least one vertex u P
if u
else Phhstart the next phaseii
for all edges uv if uv is tense
Ruv
if v is not already in the queue
Pv
Figure 8.6. Moores shortestpath algorithm. Bold red lines involving the token are only for analysis.
Because the queue contains at most one copy of each vertex at any time, each vertex is Ped from the queue at most once in each phase, and therefore each edge uv is checked for tenseness at most once in each phase. Moreover, every edge that is tense when a phase begins is relaxed during that phase. Some edges that become tense during the phase might also be relaxed during that phase, and some relaxed edges might become tense again in the same phase. Thus, M can be viewed as a refinement of BF that uses a queue to maintain tense edges, rather than testing every edge by brute force. In particular, a similar inductive proof establishes the following analogue of Lemma .:
Lemma .. For every vertex v and nonnegative integer i, after i phases of M, we have distvdisti v.
Thus, if the input graph has no negative cycles, M halts after at most V1 phases. In each phase, we scan each vertex at most once, so we relax each edge at most once, so the worstcase running time of a single phase is OE. Thus, the overall running time of M is OVE. In practice, however, M often computes shortest paths considerably faster than BF, because it only scans an edge uv if distu was changed in the previous phase.
If the input graph contains a negative cycle, M never halts. Fortunately, like BF, it is easy to modify Moores algorithm to report negative
8. SP
eee
5 1 5 1 5 1
d 3 f d 3 f d2 3 4f
7 b 5 7 b 5 7 b 5
23 s2 10 3 a b c2 9 3 686868
a 10 c a3 10 4c a3 10 4c 343434
s0s0s0 e5e5e5
5 1 5 1 5 1
d0 3 4f d0 3 4f d1 3 4f
7 b 5 7 b 5 7 b 5
2 9 3 d 2 9 3 d e2 9 3 686868
a3 10 4c a3 10 4c a3 10 4c 343434
s0s0s0
Figure 8.. A complete run of Moores algorithm on a directed graph with negative edges. Nodes are pulledfromthequeueintheorders abc d fde d,where istheendofphasetoken.At the start of each phase, bold edges indicate predecessors, and shaded vertices are in the vertex queue. Compare with Figures 8.6 and 8..
cycles if they exist. Perhaps the easiest modification is to actually maintain a token, and count the number of times the token is Ped from the queue. Then the input graph contains a negative cycle if and only if the queue is nonempty immediately after the token is Ped for the V1th time.
Dynamic Programming Formulation
Like almost everything else with his name on it, Richard Bellman derived the BellmanFord shortestpath algorithm via dynamic programming. As usual, we need to start with a recursive definition of shortest path distances. Its tempting
to use the same identity that we exploited for directed acyclic graphs: distv0 if vs
min distuwuv otherwise uv
Unfortunately, if the input graph is not a dag, this recurrence doesnt work!
Suppose the input graph contains the directed cycle uvwu. To compute distw we first need distv, and to compute distv we first need distu, but to compute distu we first need distw. If the input graph has any directed cycles, we get stuck in an infinite loop!
d f
To support a proper recurrence, we need to add an additional structural parameter to the distance function, which decreases monotonically at each recursive call, defined so that the function is trivial to evaluate when the parameter reaches 0. Bellman chose the maximum number of edges as this additional parameter.
As in our earlier analysis, let distiv denote the length of the shortest walk from s to v consisting of at most i edges. Bellman observed that this function obeys the following Bellmans equation recurrence:
80 distiv1
:min
disti1v min disti1uwuv
if i0 and vs if i0 and v 6 s
otherwise
uv
Lets assume that the graph has no negative cycles, so our goal is to compute distV1v for every vertex v. Here is a straightforward dynamicprogramming evaluation of this recurrence, where disti,v stores the value of distiv. Correctness of the final shortestpath distances follows from the correctness of the recurrence, and the OV E running time is obvious. This is essentially how Bellman presented his shortestpath algorithm.
BFDPs dist0, s 0
for every vertex v 6 s
dist0, v 1
1 to V1
for every vertex v
disti, v disti1, v for every edge uv
if disti, vdisti1, uwuv disti, v disti1, uwuv
We can transform this dynamic programming algorithm into our original formulation of BF through a short series of minor optimizations. First, each iteration of the outermost loop considers each edge uv exactly once, but the order in which we consider those edges doesnt actually matter. Thus, we can safely remove one level of indentation from the last three lines! The modified algorithm may consider edges in a dierent order, but it still correctly computes distiv for all i and v.
8.. Relax ALL the Edges: BellmanFord
for i
As well see in the next chapter, this is not the only reasonable choice.
8. SP
BFDPs dist0, s 0
for every vertex v 6 s
dist0, v 1
1 to V1
for every vertex v
disti, v disti1, v
for every edge uv
if disti,vdisti 1,u wuv
disti,v disti 1,u wuv
Next we change the indices in the last two lines from i1 to i. This change may cause the distances disti, v to approach the true shortestpath distances more quickly than before, but the algorithm correctly computes the true shortest path distances. Instead of disti, vdisti v, we now have disti, vdisti v for all i and v, mirroring Lemmas . and ..
BFDPs dist0, s 0
for every vertex v 6 s
dist0, v 1
1 to V1
for every vertex v
disti, v disti1, v
But this algorithm is a little silly. In the ith iteration of the outermost loop, we first copy the i1th row of the array dist,to the ith row, and then modify the elements of the ith row. So we really dont need a twodimensional array at all; the iteration index i is completely redundant! In our final modification, we maintain only a onedimensional array of tentative distances.
BFFs dists 0
for every vertex v 6 s
distv 1
for i 1 to V1
for every edge uv
if distvdistuwuv distv distuwuv
for i
for i
for every edge uv
if disti, vdisti, uwuv
hhnot i1!ii disti,v disti,uwuv hhnoti1!ii
6
This final dynamic programming algorithm is almost identical to our original formulation of BF! The first three lines initialize the shortest path distances, and the last two lines relax the edge uv if that edge is tense.
Exercises
BFF is missing only two features of our earlier formulation: It does not maintain predecessor pointers or detect negative cycles. Fortunately, adding those features is straightforward.
Exercises
. LetGbeadirectedgraphwitharbitraryedgeweightswhichmaybepositive, negative, or zero, possibly with negative cycles, and let s be an arbitrary vertex of G.
a Suppose every vertex v stores a number distv but no predecessor pointers. Describe and analyze an algorithm to determine whether distv is the shortestpath distance from s to v, for every vertex v.
b Suppose instead that every vertex v 6 s stores a pointer predv to another vertex in G but no distances. Describe and analyze an algorithm to determine whether these predecessor pointers define a singlesource shortest path tree rooted at s.
. A looped tree is a weighted, directed graph built from a binary tree by adding an edge from every leaf back to the root. Every edge has nonnegative weight.
58
16 4 17 0 1 42 7
23 914
A looped tree.
a How much time would Dijkstras algorithm require to compute the shortest path between two vertices u and v in a looped tree with n nodes?
b Describe and analyze a faster algorithm.
. Suppose we are given a directed graph G with weighted edges and two
vertices s and t.
a Describe and analyze an algorithm to find the shortest path from s to t when exactly one edge in G has negative weight. Hint: Modify Dijkstras algorithm. Or dont.
8. SP
8
b Describe and analyze an algorithm to find the shortest path from s to t when exactly k edges in G have negative weight. How does the running time of your algorithm depend on k?
. Suppose we are given an undirected graph G in which every vertex has a positive weight.
a Describe and analyze an algorithm to find a spanning tree of G with minimum total weight. The total weight of a spanning tree is the sum of the weights of its vertices.
b Describe and analyze an algorithm to find a path in G from one given vertex s to another given vertex t with minimum total weight. The total weight of a path is the sum of the weights of its vertices.
Hint: One of these problems is trivial.
. For any edge e in any graph G, let Ge denote the graph obtained by deleting e from G. Suppose we are given a graph G and two vertices s and t. The replacement paths problem asks us to compute the shortestpath distance from s to t in Ge, for every edge e of G. The output is an array of E distances, one for each edge of G.
a Suppose G is a directed graph, and the shortest path from vertex s to vertex t passes through every vertex of G. Describe an algorithm to solve this special case of the replacement paths problem in OE log Vtime.
TMb Describe an algorithm to solve the replacement paths problem for arbitrary undirected graphs in OE log Vtime.
In both subproblems, you may assume that all edge weights are nonnegative.
Hint: If we delete an edge of the original shortest path, how do the old and new shortest paths overlap?
. LetGV,Ebeaconnecteddirectedgraphwithnonnegativeedgeweights, let s and t be vertices of G, and let H be a subgraph of G obtained by deleting some edges. Suppose we want to reinsert exactly one edge from G back into H, so that the shortest path from s to t in the resulting graph is as short as possible. Describe and analyze an algorithm that chooses the best edge to reinsert, in OE log Vtime.
.a DescribeandanalyzeamodificationofBellmanFordthatactuallyreturns a negative cycle if any such cycle is reachable from s, or a shortestpath tree if there is no such cycle. The modified algorithm should still run in OV E time.
b Describe and analyze a modification of BellmanFord that computes the correct shortest path distances from s to every other vertex of the input graph, even if the graph contains negative cycles. Specifically, if any walk from s to v contains a negative cycle, your algorithm should end with distv1; otherwise, distv should contain the length of the shortest path from s to v. The modified algorithm should still run in OV E time.
TMc Repeat parts a and b, but for Fords generic relaxation algorithm. You may assume that the unmodified algorithm halts in O2Vsteps if there is no negative cycle; your modified algorithms should also run in O2Vtime.
. Consider the following even looser variant of Fords generic relaxation algorithm:
Prove that if FB examines the edges of any walk W starting from s, in order along W, then the last distance label in W is at most the length of W . More formally: If the edgPes of any walk v0v1v, where v0s, define a subsequence of the edges e1, e2, e3, . . . examined by FB, then we have distvi1 wvi1vi. Hint: This property is almost easier to prove than it is to state correctly.
. This problem considers several ways to detect negative cycles using Fords generic relaxation algorithm.
a Prove that if preds ever changes after ISSSP, then the input graph contains a negative cycle through s.
b Show that preds might never change after ISSSP, even when the input graph contains a negative cycle through s.
c Let P denote the current graph of predecessor edges predvv, and let X denote the set of all currently tense edges; both of these sets evolve as the algorithm executes. Prove that the input graph has no negative cycles if and only if PX is always a dag.
d Let R denote the set of all edges that have been relaxed so far; this set grows as the algorithm executes. Prove that the input graph has no negative cycles if and only if R is always a dag.
Exercises
FBs:
ISSSPs
for i 1 to whatever, man, I dont care
ei any edge in G if ei is tense
Rei
8. SP
TM. Prove that Dijkstras algorithm performs 2Vrelaxations in the worst case when edges are allowed to have negative weight, even if the underlying graph is acyclic. Specifically, for every positive integer n, construct a nvertex dag Gn with weighted edges, such that Dijkstras algorithm calls R 2n times when Gn is the input graph. Hint: Binary counter.
TM. Prove that Fords generic relaxation algorithm and therefore Dijkstras algorithm halts after at most O2Vrelaxations, unless the input graph contains a negative cycle. Hint: See Problem d.
. Suppose you are given a directed graph G in which every edge has negative weight, and a source vertex s. Describe and analyze an ecient algorithm that computes the shortestpath distances from s to every other vertex in G. Specifically, for every vertex t:
If t is not reachable from s, your algorithm should report distt1.
IfGhasacyclethatisreachablefroms,andtisreachablefromthatcycle, then the shortestpath distance from s to t is not welldefined, because there are paths formally, walks from s to t of arbitrarily large negative length. In this case, your algorithm should report distt1.
If neither of the two previous conditions applies, your algorithm should report the correct shortestpath distance from s to t.
. Althoughwetypicallyspeakoftheshortestpathbetweentwonodes,single graph could contain several minimumlength paths with the same endpoints. Even for weighted graphs, it is often desirable to choose a minimumweight path with the fewest edges; call this a best path from s to t. Suppose we are given a directed graph G with positive edge weights and a source vertex s in G. Describe and analyze an algorithm to compute best paths in G from s to every other vertex.
14 14 14 14 21212121
24321 24321 24321 24321 11111111 23535 23535 23535 23535 24242424
Figure 8.8. Four of many equallength shortest paths. The rst path is the best shortest path.
. Describe and analyze an algorithm to determine the number of shortest paths from a source vertex s to a target vertex t in an arbitrary directed graph G with weighted edges. You may assume that all edge weights are positive and that all necessary arithmetic operations can be performed in
O1 time. Hint: Compute shortest path distances from s to every other vertex. Throw away all edges that cannot be part of a shortest path from s to another vertex. Whats left?
. You just discovered your best friend from elementary school on Twitbook. You both want to meet as soon as possible, but you live in two dierent cites that are far apart. To minimize travel time, you agree to meet at an intermediate city, and then you simultaneously hop in your cars and start driving toward each other. But where exactly should you meet?
You are given a weighted graph GV, E, where the vertices V represent cities and the edges E represent roads that directly connect cities. Each edge e has a weight we equal to the time required to travel between the two cities. You are also given a vertex p, representing your starting location, and a vertex q, representing your friends starting location.
Describe and analyze an algorithm to find the target vertex t that allows you and your friend to meet as quickly as possible.
. You are hired as a cyclist for the Giggle Highway View project, which will provide streetlevel images along the entire US national highway system. As a pilot project, you are asked to ride the Giggle HighwayView Fixed Gear CarbonFiber Bicycle from the Giggleplex in Portland, Oregon to
Gigglesburg in Williamsburg, Brooklyn, New York.
You are a hopeless caeine addict, but like most Giggle employees you are also a coee snob; you only drink independently roasted, handpulled, directtrade, organic, shadegrown, singleorigin espresso, unadulterated by milk or sugar, thank you very much. After each espresso shot, you can bike up to L miles before suering a caeinewithdrawal migraine.
Giggle helpfully provides you with a map of the United States, in the form of an undirected graph G, whose vertices represent coee shops that sell independently roasted handpulled directtrade organic shadegrown single origin espresso, and whose edges represent highway connections between them. Each edge e is labeled with the length e of the corresponding stretch of highway. Naturally, there are acceptable espresso stands at both Giggle oces, represented by two specific vertices s and t in the graph G.
a Describe and analyze an algorithm to determine whether it is possible to bike from the Giggleplex to Gigglesburg without suering a caeine withdrawal migraine.
b You discover that by wearing a more expensive fedora, you can increase the distance L that you can bike between espresso shots. Describe and analyze and algorithm to find the minimum value of L that allows
Exercises
8. SP
you to bike from the Giggleplex to Gigglesburg without suering a caeinewithdrawal migraine.
c When you report to your supervisor whom Giggle recently hired away from their competitor Unter that the ride is impossible, she demands to look at your map. Oh, I see the problem; there are no Starbucks on this map! As you look on in horror, she hands you an updated graph G0 that includes a vertex for every Starbucks location in the United States, helpfully marked in Starbucks Green PantoneC.
Describe and analyze an algorithm to find the minimum number of Starbucks locations you must visit to bike from the Giggleplex to Gigglesburg without suering a caeinewithdrawal migraine. More formally, your algorithm should find the minimum number of green vertices on any path in G0 from s to t that uses only edges of length at most L.
. Suppose you are given a directed graph GV, E with nonnegatively weighted edges and two vertices s and t. Describe and analyze an algorithm to find the shortest walk in G from s to t possibly repeating vertices andor edges whose number of edges is divisible by 3.
For example, given the graph shown below, with the indicated vertices s and t, and with all edges having weight 1, your algorithm should return 6, which is the length of the walk swyxswt has length .
swt
xyz
. Suppose you are given a directed graph G with nonnegatively weighted edges, where some edges are red and the remaining edges are blue. Describe an algorithm to find the shortest walk in G from one vertex s to another vertex t in which no three consecutive edges have the same color. That is, if the walk contains two red edges in a row, the next edge must be blue, and if the walk contains two blue edges in a row, the next edge must be red.
For example, given the following graph as input, where every red edge has weight 1 and every blue edge has weight 2, your algorithm should return the integer 9, because the shortest legal walk from s to t is s!a!bd!ca!b!c.
sab
cdt
. Consider a directed graph G, where each edge has a nonnegative weight, and each edge is colored either red, white, or blue. A walk in G is called a French flag walk if its sequence of edge colors is red, white, blue, red, white, blue, and so on. More formally, a walk v0v1vk is a French flag walk if, for every integer i, the edge vivi1 is red if i mod 30, white if i mod 31, and blue if i mod 32.
Describe an algorithm to find the shortest French flag walks from one starting vertex s to every other vertex in G.
. There are n galaxies connected by m intergalactic teleportways. Each teleportway joins two galaxies and can be traversed in both directions. Also, each teleportway e has an associated cost of ce dollars, where ce is a positive integer. A teleportway can be used multiple times, but the toll must be paid every time it is used.
Judy wants to travel from galaxy s to galaxy t as cheaply as possible. However, she wants the total cost to be a multiple of five dollars, because carrying small change is not pleasant either.
a Describe and analyze an algorithm to compute the minimum total cost of traveling from galaxy s to galaxy t, subject to the restriction that the total cost is a multiple of five dollars.
b Solve part a, but now assume that Judy has a coupon that allows her to use exactly one teleportway for free.
. After moving to a new city, you decide to choose a walking route from your home to your new oce. To get a good daily workout, your route must consist of an uphill path for exercise followed by a downhill path to cool down, or just an uphill path, or just a downhill path. Youll walk the same path home, so youll get exercise one way or the other. But you also want the shortest path that satisfies these conditions, so that you actually get to work on time.
Your input consists of an undirected graph G, whose vertices represent intersections and whose edges represent road segments, along with a start vertex s and a target vertex t. Every vertex v has an associated value hv, which is the height of that intersection above sea level, and each edge uv has an associated value uv, which is the length of that road segment.
a Describe and analyze an algorithm to find the shortest uphilldownhill walk from s to t. Assume all vertex heights are distinct.
b Now suppose we allow some or all vertex heights to be equal. Describe and analyze an algorithm to find the shortest uphill then downhill walk from s to t; you may use flat edges in both the uphill and downhill portions of your walk.
Exercises
8. SP
c Finally, suppose you discover that there is no path from s to t with the structure you want. Describe an algorithm to find a path from s to t that alternates between uphill and downhill subpaths as few times as possible, and has minimum length among all such paths.
. After graduating from ShamPoobanana University you accept a job with AerophobesRUs, the leading traveling agency for people who hate to fly. Your job is to build a system to help customers plan airplane trips from one city to another. All of your customers are afraid of flying and by extension, airports, so any trip you plan needs to be as short as possible. You know all the departure and arrival times of all the flights on the planet.
Suppose one of your customers wants to fly from city X to city Y. Describe an algorithm to find a sequence of flights that minimizes the total time in transitthe length of time from the initial departure to the final arrival, including time at intermediate airports waiting for connecting flights.
. In Exercisefrom Chapter , you designed an algorithm to decide whether a given acuteangle maze is solvable. In this problem, you will design algorithms to find the shortest walk through a given acuteangle maze, for two dierent definitions of length.
Complete each angle maze below by tracing a path from start to nish that has only acute angles.
Start Finish
Start Finish
Your input is a connected undirected graph G whose vertices are points in the plane and whose edges are line segments. Edges do not intersect, except at their endpoints. For example, a drawing of the letter X would have five vertices and four edges; the first maze above hasvertices andedges. You are also given two vertices Start and Finish.
A walk from Start to Finish in G is valid if it contains only acute angles, or more formally, for any two consecutive edges uvw, either uvw or 0uvw2. Assume you can determine in O1 time whether the angle between two given segments is straight, obtuse, right, or acute.
a Describe an algorithm to compute a valid walk from Start to Finish that traverses as few segments as possible. If your walk traverses the same segment twice, count it twice.
b Describe an algorithm to compute a valid walk from Start to Finish that makes as few turns as possible. Hint: This is not the same as part a.
Exercises
c DescribeanalgorithmtocomputeavalidwalkfromStarttoFinishwhose total Euclidean length is as small as possible. Assume you can also compute the length of any segment in O1 time.
. After a grueling midterm at the SeeBull Center for Fake News Detection, you decide to take the bus home. Since you planned ahead, you have a schedule that lists the times and locations of every stop of every bus in ShamPoobanana. Unfortunately, no single bus visits both the SeeBull Center and your home; you must change buses at least once. There are exactly b dierent buses. Each bus starts at ::, makes exactly n stops, and finally stops running at ::. Buses always run exactly on schedule, and you have an accurate watch. Finally, you are far too tired to walk between bus stops.
a Describe and analyze an algorithm to determine the sequence of bus rides that gets you home as early as possible. Your goal is to minimize your arrival time, not the time you spend traveling.
b Oh, no! The midterm was held on Halloween, and the streets are infested with zombies! The ShamPoobanana Mass Transit District doesnt have the funding to add additional buses or install zombieproof bus stops, especially for only one night a year. Describe and analyze an algorithm to determine a sequence of bus rides that minimizes the total time you spend waiting at bus stops; you dont care how late you get home or how much time you spend on buses. Assume you can wait inside the SeeBull Center until your first bus is just about to leave.
. The first morning after returning from a glorious spring break, Alice wakes to discover that her car wont start, so she has to get to her classes at ShamPoobanana University by public transit. She has a complete transit schedule for Poobanana County. The bus routes are represented in the schedule by a directed graph G, whose vertices represent bus stops and whose edges represent bus routes between those stops. For each edge uv, the schedule records three positive real numbers:
uv is the length of the bus ride from stop u to stop v in minutesfuvisthefirsttimeinminutespastamthatabusleavesstopu
for stop v.
uv is the time between successive departures from stop u to stop v
in minutes.
Thus, the first bus for this route leaves u at time f uv and arrives at v at time f uvuv, the second bus leaves u at time f uvuv and arrives at v at time f uvuvuv, the third bus leaves u at time
8. SP
f uv2uv and arrives at v at time f uv2uvuv, and so on.
Alice wants to leaves from stop s her home at a certain time and arrive at stop t The SeeBull Center as quickly as possible. If Alice arrives at a stop on one bus at the exact time that another bus is scheduled to leave, she can catch the second bus. Because shes a student at SPU, Alice can ride the bus for free, so she doesnt care how many times she has to change buses.
Describe and analyze an algorithm to find the earliest time Alice can reach her destination. Your input consists of the directed graph GV, E, the vertices s and t, the values e, f e, e for each edge e 2 E, and Alices starting time in minutes past am.
Hint: In this rare instance, it may be easier to modify the algorithm, instead of modifying the input graph.
. Mulder and Scully have computed, for every road in the United States, the exact probability that someone driving on that road wont be abducted by aliens. Agent Mulder needs to drive from Langley, Virginia to Area , Nevada. What route should he take so that he has the least chance of being abducted?
More formally, you are given a directed graph GV, E, where every edge e has an independent safety probability pe. The safety of a path is the product of the safety probabilities of its edges. Design and analyze an algorithm to determine the safest path from a given start vertex s to a given target vertex t. You may assume that all necessary arithmetic operations can be performed in O1 time.
Las Vegas, NV
0.2 0.7
0.1
0.5
0.9
Area 51, AZ
Memphis, TN
0.5
For example, with the probabilities shown above, if Mulder tries to drive directly from Langley to Area , he has a 50 chance of getting there without being abducted. If he stops in Memphis, he has a 0.70.963 chance of arriving safely. If he stops first in Memphis and then in Las Vegas, he has a 10.70.10.596.5 chance of being abducted! Thats how they got Elvis, you know.
Langley, VA
6
. On an overnight camping trip in Sunnydale National Park, you are woken from a restless sleep by a scream. As you crawl out of your tent to investigate, a terrified park ranger runs out of the woods, covered in blood and clutching a crumpled piece of paper to his chest. As he reaches your tent, he gasps,
Get out. . . while. . . you. . . , thrusts the paper into your hands, and falls to the ground. Checking his pulse, you discover that the ranger is stone dead.
You look down at the paper and recognize a map of the park, drawn as an undirected graph, where vertices represent landmarks in the park, and edges represent trails between those landmarks. Trails start and end at landmarks and do not cross. You recognize one of the vertices as your current location; several vertices on the boundary of the map are labeled EXIT.
On closer examination, you notice that someone perhaps the poor dead park ranger has written a real number betweenandnext to each vertex and each edge. A scrawled note on the back of the map indicates that a number next to an edge is the probability of encountering a vampire along the corresponding trail, and a number next to a vertex is the probability of encountering a vampire at the corresponding landmark. Vampires cant stand each others company, so youll never see more than one vampire on the same trail or at the same landmark. The note warns you that stepping o the marked trails will result in a slow and painful death.
You glance down at the corpse at your feet. Yes, his death certainly looked painful. Wait, was that a twitch? Are his teeth getting longer? After driving a tent stake through the undead rangers heart, you wisely decide to immediately leave the park as fast as possible.
Describe and analyze an ecient algorithm to find a path from your current location to an arbitrary EXIT node, such that the total expected number of vampires encountered along the path is as small as possible. Be sure to account for both the vertex probabilities and the edge probabilities. Hint: Even without the vertex probabilities, this is not the same as the previous problem!
Exercises
Reviews
There are no reviews yet.