Suppose we are given an m arc, n vertex directed graph and we want to be able to

Question

Suppose we are given an m arc, n vertex directed graph and we want to be able to quickly
answer questions of the form: what is the shortest path (in terms of number of edges) from i to j? for
an arbitrary pair of vertices i; j (we return either the sequence of vertices to visit, or we return NONE
if there is no such path). We expect to be answering many such queries, so we will rst spend some
time processing the graph and storing information so we can then quickly answer any such query. As
a baseline, we could plan to construct an n n table P where each entry P[i; j] is a pointer to a linked
list of the vertices on the shortest path. Note that once the table is built, it take to (k) time to
answer a query for a given i; j that has a best path with k edges.

A How could we construct such a table P[i; j] eciently? What is the time and space to build it?

B Suppose we still want to we able to answer queries in time (k), but we want to reduce the space
used by the baseline solution. Describe a solution that uses O(n^2) space and give the pre-processing
time.
C Now suppose we have an undirected graph and we just want to be able to answer queries of the
form: is there a path from u to v? Describe an ecient algorithm to preprocess the graph to quickly
answer such queries. A good answer would have fast preprocessing time, use little space, and answer
such queries in O(1) time.

Explanation / Answer

Use the algorithm called Floyd Warshall's "All pair shortest path" that calculates the shortest distance between all the pairs of vertices, and can be stored in a matrix . Need to be done just once and cant be used multiple times. Psuedocode 1 /* Assume a function edgeCost(i,j) which returns the cost of the edge from i to j 2 (infinity if there is none). 3 Also assume that n is the number of vertices and edgeCost(i,i) = 0 4 */ 5 6 int path[][]; 7 /* A 2-dimensional matrix. At each step in the algorithm, path[i][j] is the shortest path 8 from i to j using intermediate vertices (1..k-1). Each path[i][j] is initialized to 9 edgeCost(i,j). 10 */ 11 12 procedure FloydWarshall () 13 for k := 1 to n 14 for i := 1 to n 15 for j := 1 to n 16 path[i][j] = min ( path[i][j], path[i][k]+path[k][j] );

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.