Given an undirected simple weighted graph G = (V, E) (having no loops or multi-edges) with two designated vertices s,t ∈ V and weight we (unnecessarily positive) for any edge e ∈ E. A path ps,t is said to be shortest from s to t if the aggregate weight of ps,t, defined as c(ps,t) = ô°€edge e∈ps,t we, is the smallest among all paths from s to t. A second smallest path is a path p′s,t with c(p′s,t) ≥ c(ps,t) and contains at least one different edge from ps,t, while c(p′s,t) ≤ c(q) for any other s âˆ' t path q.

1. Design an algorithm to find such a second smallest s âˆ' t path. Please describe your algorithm and sketch its correctness. Pseudocode is NOT required.

2. Two (or more) paths are edge-disjoint if they have no edges in common. The K shortest Edge- Disjoint Path Problem is to find the shortest, 2nd shortest, · · · , K th shortest s âˆ' t paths which are Edge-Disjoint. Design an algorithm to find these K paths. Please describe your algorithm and sketch its correctness. Pseudocode is NOT required. (HINT: translate this into a flow problem. )

3. Two (or more) paths are node-disjoint if they have no common intermediate nodes. Design an algorithm to find the K shortest Node-Disjoint Paths. Please describe your algorithm and sketch it- s correctness. Pseudocode is NOT required. (HINT: Convert to K shortest Edge-Disjoint Path Problem.)