The purpose of this exercise, due to Shier [1979], and Guerriero, Lacagnina, Musmanno, and Pecorella [1997], is to introduce an approach for extending the generic algorithm to the solution of a class of multiple shortest path problems. Consider the single origin/many destinations shortest path context, where node 1 is the origin, assuming that no cycles of negative length exist. Let di(1) denote the shortest distance from node 1 to node i. Sequentially, for k = 2, 3,..., denote by di(k) the minimum of the lengths of paths from 1 to i that have length greater than di(k - 1) [if there is no path from 1 to i with length greater than di(k - 1), then di(k) = ∞]. We call di(k) the k-level shortest distance from 1 to i.
