Sometimes, it's good to have alternatives. Supposed you've just moved to a new city. You want...

Transcribed Image Text:

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 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