graph - 图中最短路径的数量

Question

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

如何在有向图中和线性时间中找到两个顶点之间不同最短路径的数量？

但我不太明白。有人可以把算法写下来，以便我能更好地理解它吗？

Answer 1

假设你需要从 src 到 dest。

对于每个顶点 x，关联两个值 count 和 val，其中 count 是从 src 到 x 的最短路径数，val 是从 src 到 x 的最短距离。还要维护一个visited 变量，告知这是否是第一次访问该节点。

应用通常的 BFS 算法，

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

第一次访问一个节点，从src到现在的u只有一条路径，所以到v的最短路径是（1+到u的最短路径），通过最短路径到达v的路径数相同as count[u] 因为说 u 有 5 种方式从源到达，那么只有这 5 种方式可以扩展到 v 因为 v 第一次通过 u 遇到，所以

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

如果 v 已经被访问过，这意味着存在通过其他一些顶点到达 v 的其他路径，那么会出现三种情况：

1. 案子val[v] == val[u]+1

如果当前 val[v]（通过其他路径到达 v）等于 val[u]+1，即我们使用通过 u 的当前路径和到达 v 的其他路径到达 v 的最短距离相等，那么到 v 的最短距离保持不变，但路径数会随着到达 u 的路径数而增加。

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

2. 案子val[v] > val[u]+1

由于我们使用 BFS 逐级遍历节点，这种情况不会发生：图是未加权的，所以我们第一次设置 val[v] 时，保证 val[v] 已经包含最短路径的长度从 src 到 v。

3. 案子val[v] < val[u]+1

在这种情况下，无需更改 val[v] 和 count[v] 的值，因为该路径不算最短路径

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