(Dijkstra and negative edge weights 15 points) Let G (V, E) be a weighted directed graph. For the rest of this problem, assume that s,t e Vand that thereais a direct path from s to t. The weights on G could be anything: negative, zero, or positive. Fortherest ofthis problem, refer to the implementation of Dijkstra's algorithm given bythe pseudocode below Dijkstra st _path(G, s, t): for all v in V,set d[v] - oo for all v in V, set p[v] - Nonte // we will use the information p[v] to reconstruct the path at the end while F isn't empty: x - a vertex v in F so that d[v] is minimized for y in x. outgoing _neighbors: d[y] - min(dy], d[x] + weight(x y)) if d[y] was changed in the previous line, set p[y] = x F.remove(x) D. add(x) // use the information in p to reconstruct the shortest path: path - [t] current t while current- s: current - p[current] add current to the front of the path return path, d[t] Notice that the pseudocode above differs from the pseudocode in the power point: first it runs Dijkstra's algorithm (as presented in the power point), and then it uses this to compute the shortest path from s to t. It returns the shortest path and the cost of that path. (a) Step through Dijkstra st path(G, s,t) on the graph G shown below. Complete the table below to shovw what the arrays dand p are at each step of the algorithm, and indicate what path is returned and what its cost is 2 4