Consider a digraph D = (V; A) with two distinct vertices s and t. (a) Let F denote the set of edges in A which appear in some shortest s-t path ( in terms of the number of edges) in D. Give an algorithm to output F in O (m + n) time.
(b) Give an algorithm to Önd an inclusion-wise maximal (not necessarily) edge-disjoint shortest s-t paths in D in O (m + n) time.