Describe and analyze an algorithm to determine the number ofshortest paths from a source vertex s to a target vertex t in anarbitrary directed graph G with weighted edges. You may assume thatall edge weights are positive and that all necessary arithmeticoperations can be performed in O(1) time.
[Hint: Compute shortest path distances from s to every othervertex. Throw away all edges that cannot be part of a shortest pathfrom s to another vertex. What’s left?]
Write a pseudo code algorithm for the situation described above.:)
