Counting shortest paths in a non-directed graph using BFS

[evinda]

Hello! (Wave)

A non-directed graph $G=(V,E)$ and two nodes $v$ and $u$ of $G$ are given. Give an algorithm that calculates the number of shortest paths $v-u$ in $G$. (The algorithm doesn't have to print all the paths, just how many exist.) The algorithm should run in time $O(n+m)$ for a graph with $n$ vertices and $m$ edges. Is it like that?

We apply BFS. At the point where we add the nodes in the queue, we calculate also the number of nodes.

 

[Nono713]

What do you think? Have you tried implementing it to see if it sort of works, try and measure the complexity, ...?