graph algorithms be weighted directed graph with vertices design variation - let of floyd-warshall' algorithm for computing the lengths of the shortest paths from each vertex to every other vertex in ( time - design an efficient algorithm for finding longest directed path from specify the vertex to vertex of an acyclic weighted directed graph graph representation used and any auxiliary data structures used alsoanalyze the time complexity of your algorithm - an independent set of an undirected graph (veis subset of such that no two vertices in are adjacent that isif and are in ithen (uvis not in maximal independent set is an independent set such thatif we were to add any additional vertex to mthen it would not be independent any more every graph has maximal independent set (can you see thisthis question is not part of the exercisebut it is worth thinking about give an efficient algorithm that computes maximal independent set for graph what is this method' running timec- give an example of an -vertex simple graph that causes dijkstra' algorithm to run in ( log ntime when its implemented with heap with negative-weight - give an example of weighted directed graph edgesbut no negative-weight cyclesuch that dijkstra' algorithm incorrectly computes the shortest-path distances from some start vertex - consider the following greedy strategy for finding shortest path from vertex start to vertex goal in given connected graph initialize path to start initialize set visited to {start if start=goalreturn path and exit otherwisecontinue find the edge (start,vof minimum weight such that is adjacent to start and is not in visited add to path add to visited set start equal to and go to step does this greedy strategy always find shortest path from start to goaleither explain intuitively why it worksor give counterexample - our implementation of shortest path lengths in code fragment relies on use of "infinityas numeric valueto represent the distance bound for vertices that are not (yetknown to be reachable from the source reimplement that function without such sentinelso that verticesother than the sourceare not added to the priority queue until it is evident that they are reachable - show that if all the weights in connected weighted graph are distinctthen there is exactly one minimum spanning tree for