Problem 1. [10 pts] [Count Shortest Paths] Given a connected undirected graph G = (V, E) and a start vertex s € V, we ca

[answerhappygod]

Problem 1 10 Pts Count Shortest Paths Given A Connected Undirected Graph G V E And A Start Vertex S V We Ca 1 (42.83 KiB) Viewed 35 times

Problem 1. [10 pts] [Count Shortest Paths] Given a connected undirected graph G = (V, E) and a start vertex s € V, we can apply the BFS algorithm to find the length of the shortest path from s to every other vertex u in G. It is clear that there could be multiple shortest paths from s to u, i.e., distinct paths from s to u that have the same length, and are all shortest paths from s to u. Give a modification of BFS algorithm to find the number of shortest paths from given s € V to every other vertex u in G that runs in the same time as BFS.