Question

NAME . You are given a strongly connected directed graph G (V, E) with positive edge weights along with a particular node vo E V. Give an efficient algorithm for finding shortest paths between all pairs of nodes, with the one restriction that these paths must all pass through v (8 points)

Answer 1

The shortest path between two nodes u and v that passes through v0 must be the shortest path from u to v0 and the shortest path from v0 to v. We can easily compute the latter using Dijkstra’s algorithm in O ((n + m) lg n) time. To compute the former, observe that we want to compute the shortest paths from every vertex to v0. This is exactly the opposite of the shortest path problem, so we can solve it easily by first reversing the graph and then running Dijkstra’s algorithm to compute the shortest paths from v0 to each vertex in GR. Reversing the graph takes linear time (as shown in the previous assignment) so this also takes O ((n + m) lg n) time. Storing all of the shortest path lengths would require O (n 2 ) time and space, so we simply keep these two arrays of shortest paths. Using these we can answer a shortest path length query from u to v by adding the shortest path length from u to v0 (in the second array we created) and the shorteste path length from v0 to v (using the first array).