We are given a directed graph G $=($V$,$ E$)$ with positive

weight function: w : E $->$ R$>0,$ and two vertices s$,$ t in V $.$ Suppose we have already

computed the d and $\backslash$pi array using the Dijkastra$$s algorithm: d$[$v$]$ is the length of the

shortest path from s to v$,$ and $\backslash$pi $[$v$]$ is the vertex before v in the path.

Please design a dynamic programming algorithm $($i$.$e$.,$ Define sub$-$problems, establish

recurrence relations between sub$-$problems, compute the base case, write the dynamic

$2$

programming algorithm pseudo$-$code$)$ to count the number of shortest paths from s to t

in O$($n log n $+$ m$)$ time where n $=|$V $|$ and m $=|$E$|.$

Hint: use the d and $\backslash$pi array to help solve the counting problem. You do not need to

worry about the integer overflow issue. That means, you assume a word can hold a very

big integer, and basic operations over these big integers take O$(1)$ time.