当给定一个有顶点和边的图 G |V|和|E|分别和顶点u和t，写一个O(|E|+|V|)算法来计算从u到t的最短路径的数量，即如果有5条长度为4的路径，其中长度4是从u的最短路径到 t 那么算法将输出 5。
我知道该算法必须以某种方式结合 DFS 或 BFS，因为它的运行时间都是 O(|E|+|V|) 运行时间，但我有点卡住了。我尝试实现一些东西，它会重复执行 DFS，算法在 t 处终止，但这对于决定将哪些节点设置为已访问以及在每次迭代后将哪些节点重置成为问题。
提前致谢!
最佳答案
您可以使用广度优先搜索。对于每个顶点，跟踪:
- 从 u 到该顶点的最短路径长度
- 每当您处理给定的顶点时，您都会为尚未设置此属性的所有邻居设置此属性。
- 这兼作“已入队”标志:您最初设置为标记值，例如 ɴɪʟ 或 ∞，并且仅对任何给定顶点更新一次。因此，您不需要单独的标志来跟踪访问过的顶点。
- 从 u 到该顶点的最短路径数
- 每当您处理给定的顶点时，您都会为其所有邻居适当增加此属性，这些邻居距 u 的最短路径长度大于您正在处理的顶点的路径。
- 请注意，您会为某些顶点多次更新此属性，但这没关系，因为您只为每条边更新一次。
关于algorithm - O(E+V) 算法计算给定图上 2 个节点之间的最短路径数，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/55736046/