graph - 图中最短路径的数量

Question

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

How to find the number of different shortest paths between two vertices, in directed graph and with linear-time?

但是我不太明白。有人可以用其他方式写下算法，以便我可以更好地理解它吗？

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 

第一次访问节点时，它只有一条从src到现在通过u的路径，因此到v的最短路径是（1 +到u的最短路径），并且通过最短路径到达v的方法数目相同之所以用count [u]表示，是因为说u有5种从源头到达的方式，所以只有这5种方式可以扩展到v，因为第一次通过u遇到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  

如果当前的val [v]（通过其他路径到v的距离）等于val [u] +1，即我们有相等的最短距离，即使用通过u的当前路径和到v的另一路径到达v的距离，则直到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的路径数。