Interview Question
AnalystsCountry: India
Yes if it is not a waited graph. It can be done by slightly modifying BFS algorithm.
for u , v E all edges connected to u. // just a reference from bfs algo
if v is already marked gray and check if d (v) == d(u) + 1, increment number of shortest paths to v by 1
otherwise if v is white set number of shortest path to 1, d(v) = d(u) +1.
You can also modify dijkstra's Algorithm but complexity would increase (in case of weighted graph).
Which company?
- Anonymous May 06, 2012