Let _ G be a weighted directed graph with n vertices. Design a variation of Floyd-Warshall’s algorithm for computing the lengths of the shortest paths from each vertex to every other vertex in O ( n 3...

Let _G
be a weighted directed graph with
n
vertices. Design a variation

of Floyd-Warshall’s algorithm for computing the lengths of the shortest

paths from each vertex to every other vertex in
O(n
³) time.

Design an efficient algorithm for finding a

longest

directed path from a

vertex
s
to a vertex
t
of an acyclic weighted directed graph _G. Specify the

graph representation used and any auxiliary data structures used. Also,

analyze the time complexity of your algorithm.