Question 18.2: How many candidates are there for an optimal solution to a s......
How many candidates are there for an optimal solution to a subproblem with the destination v? (Let n denote the number of vertices in the input graph. The in- and outdegree of a vertex is the number of incoming and outgoing edges, respectively.)
a) 2
b) 1 + the in-degree of v
c) 1 + the out-degree of v
d) n
(See Section 18.2.9 for the solution and discussion.)
Correct answer: (b). The optimal substructure lemma (Lemma 18.1) is stated as if there were two candidates for an optimal solution, but Case 2 comprises several subcases, one for each possible final hop (w, v) of an s-v path. The possible final hops are the incoming edges at v. Thus, Case 1 contributes one candidate and Case 2 a number of candidates equal to the in-degree of v. This in-degree could be as large as n − 1 in a directed graph (with no parallel edges), but is generally much smaller, especially in sparse graphs.