USC Admissions Center needs your help in planning paths forCampus tours

given to prospective students or interested groups. Let USCcampus be modeled

as a weighted, directed graph G containing locationsV connected by one-way

roads E. On a busy day, let k be the number ofcampus tours that have to be

done at the same time. It is required that the paths of campustours do not

use the same roads. Let the tour have k startinglocations A = { a1, a2,...,ak

} ? V . From the starting locations the groupsare taken by a guide on a path

through G to some ending location in B ={ b1, b2,..., bk }? V . Your goal is

to find a path for each group i from the startinglocation, ai , to any ending

location bj such that no two paths share anyedges, and no two groups end in

the same location bj .

a. Design an algorithm to find k pathsai ? bj that start andend at different

vertices and such that they do not share any edges.

b. Modify your algorithm to find k pathsai ? bj , that startand end in different

locations and such that they share neither vertices noredges.