图中最短路径的数量

Question

我需要使用广度优先搜索来查找图中两个节点之间的所有路径数量。我认为我的问题的答案可以在这里找到： 如何在有向图中以线性时间查找两个顶点之间不同最短路径的数量？，但我不太理解，请问是否能用其他话语将算法写下以便于我更好地理解？

- Miroslav Lhoťan

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到now通过u的路径，因此到v的最短路径是(1 +到u的最短路径)，到达v的最短路径的方式数量与count[u]相同，因为假设u有5种从源头到达的方式，则只有这5种方式可以被扩展到v，因为v是通过u第一次遇到的。

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

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

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

如果当前的val[v]（即通过u和到v的其他路径达到v的距离）等于val[u]+1，这意味着我们使用当前路径通过u到达v和到v的另一条路径具有相同的最短距离，则到v的最短距离保持不变，但是到达u的路径数量增加。

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

2. 当我们使用 BFS 逐层遍历节点时，这种情况不会发生：图是无权的，因此第一次设置 val[v] 时，保证 val[v] 已经包含了从 src 到 v 的最短路径长度。

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

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

- Shashwat Kumar

---

另外，我应该在哪里增加计数值？当我从源顶点开始时，计数为零，那么一直到最后都是零。 - Miroslav Lhoťan

没有访问记录表示它已经被访问过了。此时它不需要在队列中。 至于计数，那是我的错误。将count [src]初始化为1，因为从源到源的到达方式数量为1。 - Shashwat Kumar

还有一个问题。它只计算最短路径吗？现在看起来它计算所有可能的路径。 - Miroslav Lhoťan

在情况2（val [v]> val [u] +1）中。如答案所述，我们显然需要更新count [v]和val [v]，假设为count [v]'和val [v]'。难道我们不应该还要更新任何节点z，其中val [z]已经设置为val [v] +1，以val [v]' +1？此外，我认为我们不应该在遇到目的地时立即停止。例如，考虑多条边以dest结尾的情况，其中两条是最短路径的一部分。 - alampada

是的，你说得对，终止条件不应该在找到目标后立即执行。我不知道为什么当时想不到这一点。关于你提出的第一个问题，你又是正确的，但由于这是BFS，所以这种情况（val[v]>val[u]+1）不会发生，因为你是逐层遍历的。我想我那时候也没有注意到这一点。感谢你指出了这些错误。 - Shashwat Kumar