Page 1 of 1
Problem 1. [10 pts] [Count Shortest Paths] Given a connected undirected graph G = (V, E) and a start vertex s € V, we ca
Posted: Thu May 05, 2022 12:55 pm
by 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 36 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.