我需要使用BFS查找图的两个节点之间的所有路径的数量。我认为我的问题的答案可以在这里找到:
How to find the number of different shortest paths between two vertices, in directed graph and with linear-time?
但是我不太明白。有人可以用其他方式写下算法,以便我可以更好地理解它吗?
最佳答案
假设您需要从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的路径数。
关于graph - 图中最短路径的数量,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/15211611/