Question 18.1: Consider an instance of the single-source shortest path prob......
Consider an instance of the single-source shortest path problem with n vertices, m edges, a source vertex s, and no negative cycles. Which of the following is true? (Choose the strongest true statement.)
a) For every vertex v reachable from the source s, there is a shortest s-v path with at most n − 1 edges.
b) For every vertex v reachable from the source s, there is a shortest s-v path with at most n edges.
c) For every vertex v reachable from the source s, there is a shortest s-v path with at most m edges.
d) There is no finite upper bound (as a function of n and m) on the fewest number of edges in a shortest s-v path.
(See Section 18.1.3 for the solution and discussion.)
Correct answer: (a). If you give me a path P between the source vertex s and some destination vertex v containing at least n edges, I can give you back another s-v path {{P}}^{\prime} with fewer edges than P and length no longer than that of P. This assertion implies that any s-v path can be converted into an s-v path with at most n−1 edges that is only shorter; hence, there is a shortest s-v path with at most n − 1 edges. To see why this assertion is true, observe that a path P with at least n edges visits at least n+1 vertices and thus makes a repeat visit to some vertex w.^{7} Splicing out the cyclic subpath between successive visits to w produces a path {{P}}^{\prime} with the same endpoints as P but fewer edges; see also Figure 15.2 and footnote 4 in Chapter 15. The length of {{P}}^{\prime} is the same as that of P, less the sum of the edge lengths in the spliced-out cycle. Because the input graph has no negative cycles, this sum is nonnegative and the length of {{P}}^{\prime} is less than or equal to that of P.
^{7}This is equivalent to the Pigeonhole Principle: Nomatter how you stuff n+1 pigeons into n holes, there will be a hole with at least two pigeons.
