算法代写 | CSCI-GA.1170-003/004 Fundamental Algorithms

这个作业是开发一种比Dijkstra单源最短路径算法更快的算法
CSCI-GA.1170-003/004 Fundamental Algorithms
Problem Set 12
Lecturer: Yevgeniy Dodis Due: 8pm on Thursday, May 7
Problem 12-1 (SSSP on a Looped Tree) 18 points
A looped tree G = (V, E) is an edge weighted directed graph built from a some (directed) binary
tree T on V rooted at some node r ∈ V , by adding an edge from every leaf in T back to r (e.g.,
if T was a long directed path, the looped tree G would be a cycle). Assume that the vertices are
labeled from 1, . . . , n, with the root r having label 1, and the edges are given in the form of an
adjacency list, along with the corresponding edge weights. Also, assume that all the edge weights
are non-negative.
Your goal will be to develop a faster than Dijkstra single source shortest path algorithm computing all shortest distances d[v] from a given input node u ∈ V to all other nodes v of G. You will
do it by solving the following sub-problems.
(a) (1 point) Show that the number of edges in G is O(n).
(b) (2 points) Compute the running time of Dijkstra’s algorithm to compute the shortest distance
d[v] from a given vertex u to v for all v ∈ V .
(c) (3 points) Modify BFS algorithm appropriately to give an O(n) algorithm to compute the
shortest distance c[v] from the root r to v, for all v ∈ V .
(d) (5 points) Give an O(n) algorithm that computes the shortest distance α from u to the root
r, for the given source vertex u. (Hint: Think of recursion, but make sure you terminate,
and fast!)
(e) (3 points) Let T = (V, E0
) be the original rooted tree you started from (before adding the
edges from the leaves of T to r). Give an O(n) algorithm to compute the shortest distance
b[v] from u to v in T (not G), for all v ∈ V .
(f) (4 points) Express (with proof) the shortest distance d[v] from u to v in terms of b[v], c[v],
and α. Use this expression to obtain an algorithm to compute d[v] for all v ∈ V with running
time asymptotically faster than the Dijkstra’s algorithm.
Problem 12-2 (Keeping things the same) 13 points
Consider a weighted, directed graph G = (V, E) with n vertices and m edges. Assume that the edges
have weights which are integers. Further, assume that G contains no negative cycles, no self-loops
and δ(u, v) < ∞ for every u 6= v ∈ V . In this question we will study the effect of perturbing the weight of an edge. Formally, your task is to design an algorithm Find-Range that takes as inputs the graph G and a particular edge e = (u, v) ∈ E. This algorithm should output the range of values, over the PS 12, Page 1 set of integers that w(u, v) can take such that all pairs of shortest distances in G would remain the same. Note that this range is non-empty as it would always include the current weight of the edge. (a) (4 points) You are given the pseudocode to fill out the algorithm. This algorithm works by making one appropriate call to an algorithm discussed in class, in a black box setting. Fill in the blanks to complete the pseudocode. Do not forget to argue the correctness and state the running time. (Hint: Under what condition is the edge (u, v) “essential”? In this case what is the value of `, r? Under what conditions is it redundant? What is the value of `, r then?) Find-Range(G, e = (u, v)) 1 Create a new graph G0 = (V, E0 ) with weights w 0 given by: w 0 (a, b) = ( if a = , b = Otherwise 2 D0 = Floyd-Warshall(W0 ). D0 has dimensions n × n. 3 if then 4 ` = , r = 5 else ` = , r = 6 return [`, r] (b) (3 points) In this question, imagine we try tosubstitute the Floyd-Warshall algorithm, on Line 2 of the previous algorithm, with a call to a SSSP algorithm. For each candidate algorithm state if the substitution is possible. Justify your choice. Additionally, if your answer is yes, explain the inputs to the algorithm. Recall that the goal of Find-Range is not to fill up the n×n matrix but to return the range [`, r]. In the previous questions you focused on the perturbation of a particular edge. In this question, we will look at perturbation of all edge weights, where defined. Specifically, you want to fill two matrices L = {`i,j}n×n, R = {ri,j}n×n with values such that the answer to Part (a) computed for every pair of vertices u, v ∈ V is the interval [`u,v, ru,v]. (c) (2 points) Let us assume that you try to implement the logic of part (a) by running FloydWarshall on graph G as opposed to graph G0 . Show that the algorithm fails by constructing a counter-example. In other words, we showed that the logic fails if we ran Floyd-Warshall directly on G. While we can run Part (a) (or possibly Part (b)) for every pair of vertices (u, v), but that would be inefficient. Instead we will modify the Floyd-Warshall Algorithm to run it on original G so we neither need to build a new G0 nor run part (a) for every pair of vertices (u, v). (d) (6 points) Modify the Floyd-Warshall Algorithm to update L, R. Use Part (a) to suitably modify the algorithm. Write the pseudocode, argue its correctness and state the running time. (Hint: Initialize L, R with W. ) PS 12, Page 2 Problem 12-3 (Number of Shortest Paths) 9 (+2) points Assume you are given a directed graph G. The goal of the question is to come up with an algorithm to compute the number of distinct shortest paths from s to the node v. The algorithm should still compute the weight of the shortest path. (a) (4 points) In the first first part you are to assume that G is an unweighted graph. Or consequently, a graph where each edge has an edge weight of 1. For each node you will update v.num which stores the number of shortest paths from s to v. Design an algorithm that updates v.num. Argue its correctness and state the running time. You will lose points for a less efficient solution. (Hint: Modify an algorithm discussed in lecture.) (b) (5 points) In the second part you are to assume that the graph G is weighted. Further, all weights w(u, v) > 0. Show how to modify Dijkstra’s algorithm we discussed in lecture to
compute v.num, the number of distinct shortest paths from s to v. Design an algorithm,
argue its correctness and state the running time. You will lose points for a less efficient
solution. You may only modify the subroutines that this algorithm calls. (Hint: Modify the
subroutines to initialize the values and then update the values.)
(c) (2 points) (Extra Credit:) In the previous part we had the condition that w(u, v) > 0. Why
was it important that w(u, v) > 0.
PS 12, Page 3