Number of shortest paths in a graph

Question

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:

How to find the number of different shortest paths between two vertices, in directed graph and with linear-time?

But I don't quite understand it. Could someone please write the algorithm down in other words so I can understand it better?

Answer 1

Let say you need to go from src to dest.

With each vertex x, associate two values count and val, where count is the number of shortest paths from src to x and val is the shortest distance from src to x. Also maintain a visited variable telling whether this is the first time visiting the node or not.

Apply usual BFS algorithm,

Initialize u = src
visited[u] = 1, 
val[u] = 0
count[u] = 1
For each child v of u,
    if v is not visited 

The first time a node is visited, it has only one path from src to now via u, so the shortest path up to v is (1 + shortest path up to 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 up to 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 means, there exists some other path up to v via some other vertices, then three cases arise:

1. case val[v] == val[u]+1

if current val[v] (which is dist up to 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 up to v, then the shortest distance up to v remains same, but the number of paths increase by number of paths of reaching u.

count[v] = count[v]+count[u]
        

2. case val[v] > val[u]+1

As we are traversing the nodes using BFS level by level, this case cannot happen: the graph is unweighted, so the first time we set val[v], it is guaranteed that val[v] will already contain the length of the shortest path from src to v.

3. case val[v] < val[u]+1

In this case, there is no need to change the values of val[v] and count[v] as this path does not count as a shortest path

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.