Shortest Paths

Prev: Minimum Spanning Trees Next: All-Pairs Shortest Paths

Exercises

0.

Let G be a directed graph with arbitrary edge weights (which may be positive, negative, or zero), possibly with negative cycles, and let s be an arbitrary vertex of G. (a) Suppose every vertex v stores a number dist(v) (but no predecessor pointers). Describe and analyze an algorithm to determine whether dist(v) is the shortest-path distance from s to v, for every vertex v. (b) Suppose instead that every vertex v \ne s stores a pointer pred(v) to another vertex in G (but no distances). Describe and analyze an algorithm to determine whether these predecessor pointers define a single-source shortest path tree rooted at s.

1.

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 non-negative weight. (a) How much time would Dijkstra’s 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.

2.

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 Dijkstra’s algorithm. Or don’t.] (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?

3.

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.]

4.

For any edge e in any graph G, let G \ e 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 shortest-path distance from s to t in G \ e, 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 $O(E\log V)$ time. (b) Describe an algorithm to solve the replacement paths problem for arbitrary undirected graphs in $O(E\log V)$ time. In both subproblems, you may assume that all edge weights are non-negative. [Hint: If we delete an edge of the original shortest path, how do the old and new shortest paths overlap?]

5.

Let $G=(V,E)$ be a connected directed graph with non-negative edge weights, 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 $O(E\log V)$ time.

6.

(a) Describe and analyze a modification of Bellman-Ford that actually returns a negative cycle if any such cycle is reachable from s, or a shortest-path tree if there is no such cycle. The modified algorithm should still run in $O(VE)$ time. (b) Describe and analyze a modification of Bellman-Ford 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 dist(v) = $-\infty$; otherwise, dist(v) should contain the length of the shortest path from s to v. The modified algorithm should still run in $O(VE)$ time. (c) Repeat parts (a) and (b), but for Ford’s generic relaxation algorithm. You may assume that the unmodified algorithm halts in $O(2^V)stepsifthereisnonegativecycle;yourmodifiedalgorithmsshouldalsorunin$O(2^V)$ time.

7.

Consider the following even looser variant of Ford’s generic relaxation

algorithm:
FellmanBored(s):
InitSSSP(s)
for i ← 1 to whatever, man, I don’t care
ei ← any edge in G
if ei is tense
Relax(ei )

Prove that if FellmanBored 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 edges of any walk $v_0\to v_1\to \cdots \to v_{\ell }$, where $v_0=s$, define a subsequence of the edges examined by FellmanBored, then

$$\mathrm{dist}(v_{\ell })\le \sum _{i=1}^{\ell }w(v_{i-1}\to v_i).$$

[Hint: This property is almost easier to prove than it is to state correctly.]

8.

This problem considers several ways to detect negative cycles using Ford’s generic relaxation algorithm. (a) Prove that if pred(s) ever changes after InitSSSP, then the input graph contains a negative cycle through s. (b) Show that pred(s) might never change after InitSSSP, even when the input graph contains a negative cycle through s. (c) Let P denote the current graph of predecessor edges pred(v) \to v, 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 P \cup X 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.

9.

Prove that Dijkstra’s algorithm performs $\Omega (2^V)$ relaxations 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 an $n$-vertex dag $G_n$ with weighted edges, such that Dijkstra’s algorithm calls Relax $\Omega (2^n)$ times when $G_n$ is the input graph. [Hint: Binary counter.]

10.

Prove that Ford’s generic relaxation algorithm (and therefore Dijkstra’s algorithm) halts after at most $O(2^V)$ relaxations, unless the input graph contains a negative cycle. [Hint: See Problem 8(d).]

11.

Suppose you are given a directed graph G in which every edge has negative weight, and a source vertex s. Describe and analyze an efficient algorithm that computes the shortest-path 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 dist(t) = $\infty$. • If G has a cycle that is reachable from s, and t is reachable from that cycle, then the shortest-path distance from s to t is not well-defined, because there are paths (formally, walks) from s to t of arbitrarily large negative length. In this case, your algorithm should report dist(t) = $-\infty$. • If neither of the two previous conditions applies, your algorithm should report the correct shortest-path distance from s to t.

12.

Although we typically speak of “the” shortest path between two nodes, single graph could contain several minimum-length paths with the same endpoints. Even for weighted graphs, it is often desirable to choose a minimum-weight 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.

13.

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 $O(1)$ 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. What’s left?]

14.

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 different 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 $G=(V,E)$, where the vertices V represent cities and the edges E represent roads that directly connect cities. Each edge e has a weight w(e) 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 friend’s 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.

15.

You are hired as a cyclist for the Giggle Highway View project, which will provide street-level images along the entire US national highway system. As a pilot project, you are asked to ride the Giggle Highway-View FixedGear Carbon-Fiber Bicycle from “the Giggleplex” in Portland, Oregon to “Gigglesburg” in Williamsburg, Brooklyn, New York. You are a hopeless caffeine addict, but like most Giggle employees you are also a coffee snob; you only drink independently roasted, hand-pulled, direct-trade, organic, shade-grown, single-origin espresso, unadulterated by milk or sugar, thank you very much. After each espresso shot, you can bike up to L miles before suffering a caffeine-withdrawal migraine. Giggle helpfully provides you with a map of the United States, in the form of an undirected graph G, whose vertices represent coffee shops that sell independently roasted hand-pulled direct-trade organic shade-grown singleorigin 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 offices, 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 suffering a caffeinewithdrawal 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 you to bike from the Giggleplex to Gigglesburg without suffering a caffeine-withdrawal migraine. (c) When you report to your supervisor (whom Giggle recently hired away from their competitor Ünter) 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 $G^{\prime }$ that includes a vertex for every Starbucks location in the United States, helpfully marked in Starbucks Green (Pantone® 3425 C). Describe and analyze an algorithm to find the minimum number of Starbucks locations you must visit to bike from the Giggleplex to Gigglesburg without suffering a caffeine-withdrawal migraine. More formally, your algorithm should find the minimum number of green vertices on any path in $G^{\prime }$ from s to t that uses only edges of length at most L.

16.

Suppose you are given a directed graph $G=(V,E)$ with non-negatively 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 and/or edges) whose number of edges is divisible by 3. For example, given the graph shown in the book, with all edges having weight 1, your algorithm should return $6$.

17.

Suppose you are given a directed graph G with non-negatively 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 graph shown in the book, your algorithm should return $9$.

18.

Consider a directed graph G, where each edge has a non-negative 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 $v_0\to v_1\to \cdots \to v_k$ is a French flag walk if, for every integer $i$, the edge $v_i\to v_{i+1}$ is red if $i\mathrm{mod}3=0$, white if $i\mathrm{mod}3=1$, and blue if $i\mathrm{mod}3=2$. Describe an algorithm to find the shortest French flag walks from one starting vertex s to every other vertex in G.

19.

There are n galaxies connected by m intergalactic teleport-ways. Each teleport-way joins two galaxies and can be traversed in both directions. Also, each teleport-way e has an associated cost of c(e) dollars, where c(e) is a positive integer. A teleport-way 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 teleport-way for free.

20.

After moving to a new city, you decide to choose a walking route from your home to your new office. 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. (You’ll walk the same path home, so you’ll 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 h(v), 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 uphill–downhill 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. (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.

21.

After graduating from Sham-Poobanana University you accept a job with Aerophobes-R-Us, 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 transit—the length of time from the initial departure to the final arrival, including time at intermediate airports waiting for connecting flights.

22.

In Exercise 20 from Chapter 5, you designed an algorithm to decide whether a given acute-angle maze is solvable. In this problem, you will design algorithms to find the shortest walk through a given acute-angle maze, for two different definitions of “length”. Complete each angle maze below by tracing a path from start to finish 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 has 14 vertices and 21 edges. 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 $u\to v$ \to w, either ∠uvw = π or 0 < ∠uvw < π/2. Assume you can determine in $O(1)$ 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).] (c) Describe an algorithm to compute a valid walk from Start to Finish whose total Euclidean length is as small as possible. (Assume you can also compute the length of any segment in $O(1)$ time.)

23.

After a grueling midterm at the See-Bull 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 Sham-Poobanana. Unfortunately, no single bus visits both the See-Bull Center and your home; you must change buses at least once. There are exactly b different buses. Each bus starts at 12:00:01am, makes exactly n stops, and finally stops running at 11:59:59pm. 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 Sham-Poobanana Mass Transit District doesn’t have the funding to add additional buses or install zombie-proof 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 don’t care how late you get home or how much time you spend on buses. (Assume you can wait inside the See-Bull Center until your first bus is just about to leave.)

24.

The first morning after returning from a glorious spring break, Alice wakes to discover that her car won’t start, so she has to get to her classes at Sham-Poobanana 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 $u\to v$, the schedule records three positive real numbers: • ($u \to v$) is the length of the bus ride from stop u to stop v (in minutes) • f ($u \to v$) is the first time (in minutes past 12am) that a bus leaves stop u for stop v. • ∆($u \to v$) 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 ($u \to v$) and arrives at v at time f ($u \to v$)+($u\to v$), the second bus leaves u at time f ($u\to v$)+∆($u\to v$) and arrives at v at time f ($u\to v$)+∆($u\to v$)+($u \to v$), the third bus leaves u at time f ($u \to v$) + 2 · ∆($u \to v$) and arrives at v at time f ($u \to v$) + 2 · ∆($u \to v$) + ($u\to v$), and so on. Alice wants to leaves from stop s (her home) at a certain time and arrive at stop t (The See-Bull 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 she’s a student at SPU, Alice can ride the bus for free, so she doesn’t 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 $G=(V,E)$, the vertices s and t, the values `(e), f (e), ∆(e) for each edge e \in E, and Alice’s starting time (in minutes past 12am). [Hint: In this rare instance, it may be easier to modify the algorithm, instead of modifying the input graph.]

25.

Mulder and Scully have computed, for every road in the United States, the exact probability that someone driving on that road won’t be abducted by aliens. Agent Mulder needs to drive from Langley, Virginia to Area 51, Nevada. What route should he take so that he has the least chance of being abducted? More formally, you are given a directed graph $G=(V,E)$, where every edge $e$ has an independent safety probability $p(e)$. 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 $O(1)$ time.

For example, if Mulder tries to drive directly from Langley to Area 51, he has a $50\%$ chance of getting there without being abducted. If he stops in Memphis, he has probability $0.7\cdot 0.9=0.63$ of arriving safely. If he stops first in Memphis and then in Las Vegas, he has probability $0.7\cdot 0.1\cdot 0.5=0.035$ of arriving safely, so his probability of being abducted is $96.5\%$.

26.

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 between 0 and 1 next 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 can’t stand each other’s company, so you’ll never see more than one vampire on the same trail or at the same landmark.) The note warns you that stepping off 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 ranger’s heart, you wisely decide to immediately leave the park as fast as possible. Describe and analyze an efficient 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!]

Prev: Minimum Spanning Trees Next: All-Pairs Shortest Paths