Suppose that a certain directed graph G in which each edge (u, v) has some length l(u, v) is given to you in the form of adjacency lists. Besides this, suppose that you are also given a 2-dimensional array D such that for vertices u, v, the value D[u, v] is the length of the shortest path from u to v (it can be if there is no such path). Give an algorithm A(G, D, s, t) that, given G, D and two nodes s, t actually finds the shortest path from s to t.

Estimate the running time of your algorithm. Estimate it also when it is known that d is an upper bound on the out degree of the points of G and l is an upper bound on the number of edges on any shortest path in G.