图中最短路径的数量

Question

我需要使用BFS找到图形的两个节点之间的所有路径的数量.我想我的问题的答案可以在这里找到:

但我不太明白.有人可以用其他的话写下算法,这样我可以更好地理解它吗？

Answer 1

假设您需要从src转到dest.

每个顶点x关联两个值count和val,count是从src到x的最短路径数,val是从src到x的最短距离.还维护一个访问变量,告知节点是否第一次到达.

应用通常的BFS算法,

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

第一次访问一个节点,因此它只有一条从源到现在通过u的路径,所以到v的最短路径是1 +最短路径到达u,并且通过最短路径到达v的方式的数量与count [u]相同,因为说你有5种方式从源头到达,那么只有这5种方式可以扩展到v,因为v是第一次遇到你的,所以

val[v] = val[u]+1,    
count[v] = count[u], 
visited[v] = 1

if v is visited

如果已经访问过v,这意味着通过其他一些顶点可以通过其他路径到达v,那么会出现三种情况:

1 :if val[v] == val[u]+1

如果通过某个其他路径向上到达v的当前val [v]等于val [u] +1,即我们使用通过u的当前路径到达v而具有相等的最短距离,而另一条路径达到v,则最短距离upto v保持不变,但路径数增加了到达u的路径数.

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

2: val[v] > val[u]+1

如果到达v的当前路径小于先前的val [v]值,则val [v]存储当前路径并且count [v]也被更新

val[v] = val[u]+1
count[v] = count[u]

第三种情况是当前路径的距离大于前一路径,在这种情况下,无需更改val [v]和count [v]的值

执行此算法直到BFS完成.最后val [dest]包含距离源最短的距离,count [dest]包含从src到dest的路径数.