graph - directed - shortest path tree example
Number of shortest paths in a graph (1)
Let say you need to go from src to dest.
With each vertex x associate two values count and val, count is the number of shortest path from src to x and val is the shortest distance from src to x. Also maintain a visited variable telling whether node is arrived first time of not.
Apply usual BFS algorithm,
Initialize u = src visited[u] = 1,val[u] = count[u] = 1 For each child v of u, if v is not visited
A node is visited first time so it has only one path from source till now via u, so shortest path upto v is 1 + shortest path upto u, and number of ways to reach v via shortest path is same as count[u] because say u has 5 ways to reach from source, then only these 5 ways can be extended upto v as v is encountered first time via u, so
val[v] = val[u]+1, count[v] = count[u], visited[v] = 1 if v is visited
If v is already visited, which mean, there way some other path upto v via some other vertices, then three cases arises:
1 :if val[v] == val[u]+1
if current val[v] which is dist upto v via some other path is equal to val[u]+1, i.e we have equal shortest distances for reaching v using current path through u and the other path upto v, then the shortest distance upto v remains same, but the numbr of path increases by number of paths of reaching u.
count[v] = count[v]+count[u] 2: val[v] > val[u]+1
If current path of reaching v is smaller than previous value of val[v], then val[v] is stored current path and count[v] is also updated
val[v] = val[u]+1 count[v] = count[u]
The third case is if current path has distance greater than previous path, in this case, no need to change the values of val[v] and count[v]
Do this algorithm till the BFS is complete. In the end val[dest] contain the shortest distance from source and count[dest] contain the number of ways from src to dest.
I need to find the number of all paths between two nodes of a graph by using BFS. I think the answer to my question can be found here:
But I don't quite understand it. Could someone please write the algorithm down in other words so I can understand it better?