2. (15 points) Critical Edges. You are given a graph G = (V, E) a weight function w : E ? 0 we increase the

2. (15 points) Critical Edges. You are given a graph G = (V, E) a weight function w : E ? <, and a source vertex s. Assume w(e) ? 0 for all e ? E.

We say that an edge e is upwards critical if by increasing w(e) by any > 0 we increase the shortest path distance from s to some vertex v ? V .

We say that an edge e is downwards critical if by decreasing w(e) by any > 0 we decrease the shortest path distance from s to some vertex v ? V (however, by definition, if w(e) = 0 then e is not downwards critical, because we cant decrease its weight below 0).

(a) (5 points) Claim: an edge (u, v) is downwards critical if and only if there is a shortest path from s to v that ends at (u, v), and w(u, v) > 0. Prove the claim above.

(b) (5 points) Make a claim similar to the one above, but for upwards critical edges, and prove it.

(c) (5 points) Using the claims from the previous two parts, give an O(E log V ) time algorithm that finds all downwards critical edges and all upwards critical edges in G