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.