# 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?