当给定一个带有顶点和边的图形 G |V|和 |E|分别和顶点 u 和 t，写一个 O(|E|+|V|(算法计算从 U 到 T 的最短路径数，即如果有 5 条长度为 4 的路径，长度为 4 是从 U 到 t 的最短路径，则算法将输出 5。
我知道该算法必须以某种方式合并 DFS 或 BFS，因为它的运行时，因为每个算法都有一个 O(|E|+|V|(运行时，但我有点卡住了。我尝试实现一些东西，它会在算法终止于 t 时重复执行 DFS，但在每次迭代后决定将哪些节点设置为访问以及重置哪些节点时，这变得存在问题。
提前感谢！
您可以使用广度优先搜索。对于每个顶点，请跟踪：
- 从 u 到该顶点的最短路径长度
- 每当处理给定顶点时，都会为尚未设置此属性的所有邻居设置此属性。
- 这兼作"已排队"标志：您最初设置为哨兵值，如 ɴɪʟ 或 ∞，并且只为任何给定顶点更新一次。因此，您不需要单独的标志来跟踪访问的顶点。
- 从 u 到该顶点的最短路径数
- 每当处理给定顶点时，对于距 u 的最短路径长度大于正在处理的顶点的路径长度的所有相邻点，都可以适当地增加此属性。
- 请注意，对于某些折点，您将多次更新此属性，但这没关系，因为每个边只更新一次此属性。