Let G = (V, E) be a directed simple graph where every vertex u has a weight w. For each vertex y, let MinWeight(y) = min{w(x) : x path(y)}, where path(y) is the set of vertices v V that can be found by a path in G from vertex y (I.E a path from y to v for all v V).

(a) Show that if we have 2 vertices s,t V, in the same strongly connected component of our graph G, then they share the same MinWeight. That is MinWeight(s) = MinWeight(t).

(b) Describe and design an efficient algorithm that for any directed acyclic graph G that finds MinWeight(z) for all vertices z V. Show that this algorithm is correct, and discuss it's running time. (Hint: Can be done in O(n+m) time)

(c) Using parts (a) and (b) design an efficient algorithm that for ANY simple directed graph G (which has real weights on all edges) finds MinWeight(z) for all vertices z V. Show that this algorithm is correct, and discuss it's running time. (Hint: This can also be done in O(n+m) time)