Sometimes, it$$s good to have alternatives.

Supposed you$$ve just moved to a new city. You want to select an apartment that has the larget number of distinct shortest paths to your workplace. Since you$$re a computer scientist, in accordance with Maslow$$s law of the hammer, you decide to solve this by representing the ciy as a graph: each road becomes a weighted edge $($weighted according to how long it takes to travel that section of road$),$ and places where the roads meet $($i$.$e$.$ intersections$)$ become nodes.

After completing this exercise, you notice something peculiar: every edge in this graph has the same weight! For convenience, you decide to declare that the weight of each edge to be $1,$ turning this into an unweighted graph. Now you just need to figure out how to calculate the number of different shortest paths.

Given an unweighted, undirected graph G $=($V$,$E$)$ representing the road network and two fixed nodes s and t within this graph $($representing a potential apartment and your new workplace, respectively$),$ devise an algorithm to find the number of different shortest paths between s and t$.$ Prove the correctness of your algorithm.

Your algorithm should run in O$(|$V $|+|$E$|)$ time. You do not need to prove the time complexity