Question: Let G = (V,E) be a directed graph in which each vertex u E V is labeled with a unique integer L(u) from the set

Let G = (V,E) be a directed graph in which each vertex u E V is labeled with a unique integer L(u) from the set { 1, 2, , VI). For each vertex u E V, let R(u) be the set of vertices that are reachable from u. Define min(u) to be the vertex in R(u) whose label is minimum. (a) (10 pts) Write pseudocode for algorithm that computes min(u) for all vertices in the graph. You will receive a 5 pt extra credit if your algorithm runs in O(IVI IE). (b) (10 pts) Prove the worst-case running time of your algorithm. (c) Extra credit (10 pts): Prove that your algorithm is correct (i.e., that it will always output the correct answer)
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
