[SOLVED] Cs6515 homework3

Graded ProblemYou are given a directed graph $G=(V,E)$ where every vertex has a label $c(v)>0$. Design an algorithm to return, for each vertex $v$, the vertex $w$ of minimum label reachable from $v$. Here, reachable means there is a path from $v$ to $w$. You may assume that $v$ is reachable from itself. Faster (in asymptotic Big O notation) and correct solutions are worth more credit.InstructionsFor the graded problems, you are allowed to use the algorithms from class as black-boxes without further explanation. These include:When using a black-box, make sure you clearly describe which input you are passing into it and how you use the output or take advantage of the data structures created by the algorithm. To receive full credit, your solution must:Unless otherwise indicated, black-box graph algorithms should be used without modification.Example: I take the input graph $G$, I first find the vertex with largest degree, call it v∗v^*v∗. I take the complement of the graph $G$, call it G′G’G′. Run Dijkstra’s algorithm on G′G’G′ with s=v∗s = v^*s=v∗ and then I get the array dist[v] of the shortest path lengths from $s$ to every other vertex in the graph G′G’G′. I square each of these distances and return this new array.We don’t want you to go into the details of these algorithms and tinker with it, just use it as a black-box as shown with Dijkstra’s algorithm above.ContextA graph theory problem is a form of reduction. You are given some problem to solve, and the challenge is to solve that problem by using one of the graph algorithms we study this semester. In other words, you reduce your problem to a graph problem such that a known algorithm can solve it for you.The known algorithms are treated as a black-box—you are not allowed to change/modify them in any way. You can (and often will) modify the original problem input in some way, or create a graph which represents the input—this becomes the input to the black-box. You then take the results of running the black-box (both its defined output and the data structures it creates during execution) and use those to deduce the solution to the original problem.RulesComponents of a complete solution(a) Describe your algorithm:(b) Justify why your algorithm is correct:(c) Analyze the runtime: