Exercise 3: Counting Shortest Paths (25 Points)
Assume an undirected, weighted, connected directed graph with positive edge weights. Given
two nodes s and t in the graph, the problem is to count the number of different shortest paths
between s and t. Give an efficient algorithm for the problem, argue its correctness, and analyze
its run time.
(Hint: Modify Dijsktra's algorithm to identify only those edges that belong to a shortest path
between s and t. Then, a DP algorithm will be used to count the number of shortest paths between
s and t. As usual, you should specify subproblems and recursive formulas for the DP algorithm.)