6.006 Quiz 2 Solutions Name 15
Problem 6. Just reverse the polarity already [10 points]
Professor Kirk has managed to get himself lost in his brand new starship. Furthermore, while
boldly going places and meeting strange new, oddly humanoid aliens, his starship’s engines have
developed a strange problem: he can only make “transwarp jump” to solar systems at distance
exactly 5 from his location.
Given a starmap represented as an unweighted undirected graph G = (V, E), where vertices repre-
sent glorious new solar systems to explore and edges represent transwarp routes, devise an efficient
algorithm to find a route (if possible) of minimum distance from Kirk’s current location s to the
location t representing Earth, that Kirk’s ship will be able to follow. Please hurry—Professor Kirk
doesn’t want to miss his hot stardate!
Solution: In general, the idea is to convert G = (V, E) into a graph G
0
= (V, E
0
) representing all
the feasible transwarp jumps that Kirk can make, i.e., with an edge (u, v) if there is a simple path
in G from u to v of length exactly 5. (Note that this definition is the notion of “distance” in the
problem, as clarified during the quiz.) Once we have such a graph G
0
, we simply run breadth-first
search on G
0
from s, and follow parent pointers from t to recover the shortest route (if there one)
for Kirk to follow. The running time of this breadth-first search is O(V + E
0
) = O(V
2
).
The central question is how to compute G
0
. The best solutions we know run in O(V
3
) time. There
are two ways to achieve this bound.
The first O(V
3
) algorithm is a modification of breadth-first search from every vertex. For each
vertex v, we construct the set N
1
(v) of all neighbors of v. Next we construct the set N
2
(v) of all
vertices reachable by a path of length 2 from v, by taking the union of N
1
(u) for each u ∈ N
1
(v).
Then we construct N
3
(v), N
4
(v), and N
5
(v) similarly. Constructing N
1
(v) costs O(V ) time, while
constructing N
k
(v) for k ∈ {2, 3, 4, 5} costs O(v
2
) time. The key here is that we remove duplicate
vertices in each set N
k
(v), so each such set has size O(V ). Because we do this for every vertex v,
we spend O(v
3
) time total. Finally we set E
0
= {(v, w) : w ∈ N
5
(v)}.
The second O(V
3
) algorithm is to compute the adjacency matrix A, and compute A
5
= A · A · A ·
A · A. Each matrix multiplication costs O(V
3
) time, for a total of O(V
3
) time. The nonzero entries
in this matrix correspond to the edges in G
0
.
A simpler O(V
4
E) = O(V
6
) algorithm is much simpler: for each vertex v
0
, for each neighbor v
1
of v
0
, for each neighbor v
2
of v
1
, for each neighbor v
3
of v
2
, for each neighbor v
4
of v
3
, for each
neighbor v
5
of v
4
, add the edge (v
0
, v
5
) to E
0
. The first two loops cost a factor of O(E), and the
next four loops cost a factor of O(V
4
).
The grading scheme was as follows. A O(V
3
) solution was worth a nominal value of 10/10. A
O(V
4
) solution was worth a nominal value of 9/10. Very few students achieved such solutions.
A O(V
4
E) or O(V
6
) solution was worth a nominal value of 7/10. These nominal values were
adjusted according to clarity, quality, and/or errors. The idea of computing a graph like G
0
was
worth a nominal value of 4/10. Executing this idea by performing a depth-5 BFS or DFS was
worth a nominal value of 5/10. Simply running BFS and focusing on the layers divisible by 5 was
worth a nominal value of 1/10.