algorithm - O(E+V) 算法计算给定图上 2 个节点之间的最短路径数

Question

当给定一个带有顶点和边的图 G |V| 和 |E| 分别和顶点 u 和 t，写一个 O(|E|+|V|) 算法来计算从 u 到 t 的最短路径的数量，即如果有 5 条长度为 4 的路径，长度 4 是从 u 的最短路径到 t 那么算法将输出 5。

我知道该算法必须以某种方式合并 DFS 或 BFS 由于其运行时间，因为每个都有 O(|E|+|V|) 运行时间，但我有点卡住了。我尝试实现一些东西，它会重复执行 DFS，算法在 t 处终止，但这对于决定将哪些节点设置为已访问以及在每次迭代后重置哪些节点变得有问题。

提前致谢！

标签： algorithmgraph-theorydepth-first-searchbreadth-first-search

Answer 1

您可以使用广度优先搜索。对于每个顶点，跟踪：

• 从u到该顶点 的最短路径长度
  • 每当您处理给定的顶点时，您都​​会为它的所有尚未设置此属性的邻居设置此属性。
  • 这兼作“已经入队”标志：您最初设置为诸如 ɴɪʟ 或 ∞ 之类的标记值，并且只对任何给定顶点更新一次。因此，您不需要单独的标志来跟踪访问的顶点。
• 从u到该顶点 的最短路径数
  • 每当你处理一个给定的顶点时，你会为它的所有从u的最短路径长度大于你正在处理的顶点的最短路径长度的邻居适当地增加这个属性。
  • 请注意，您将为某些顶点多次更新此属性，但这没关系，因为您只在每条边上更新一次。