Question $3($Shortest path$)$

$(50$ points$)$ Consider the Dijkstra's shortest path algorithm whose pseudocode is given below. Modify this algorithm such that it outputs the counts of

different shortest paths from the origin vertex to every other vertex.

Remember that in a graph, you can follow different paths to reach a destination vertex from the origin vertex. The shortest path is the one that has the

minimum total cost. Of course, there may exist more than one path with the same minimum total cost. This question asks you to find the number of such

shortest paths.

Hint: You are NOT asked to output all shortest paths from the origin to every other vertex. You are asked to output the counts of such shortest paths.

Give your answer by modifying the code in the two boxes given below. Just give the new contents of these two boxes, indicating BOX$1$ and BOX$2$ in your

answer sheet and writing the new contents. Do not write the other parts of this pseudocode in your answer sheet. Do not write an answer from scratch.

Do not give a C$++$ implementation. Such answers will not be graded.

$//$ adjMat is the adjacency matrix of a weighted directed graph G that contains N vertices. Assume that the graph contains only positive edge weights.

$//$ origin is the id of the source vertex for which it finds the shortest paths.

$//$ weight is an output array that keeps the total cost of the shortest path from the origin vertex to every other vertex.

$//$ count is an output array that keeps the number of different shortest paths from the origin vertex to every other vertex.

shortestPath$($ adjMat, $N,$ origin, weight, count $)$