evinda
Gold Member
MHB
- 3,741
- 0
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.
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.