O(E+V) 算法计算给定图上 2 个节点之间的最短路径数
O(E+V) algorithm to compute number of shortest paths between 2 nodes on given graph
当给定一个有顶点和边的图 G |V|和|E|分别和顶点u和t，写一个O(|E|+|V|)算法来计算从u到t的最短路径的数量，即如果有5条长度为4的路径，其中长度4是从u的最短路径到 t 那么算法将输出 5.
我知道该算法必须以某种方式包含 DFS 或 BFS，因为它的 运行-time 因为每个算法都有 O(|E|+|V|) 运行-time ，但我有点卡住了。我尝试实现一些东西，它会重复执行 DFS，算法在 t 处终止，但这对于决定将哪些节点设置为已访问以及在每次迭代后将哪些节点重置成为问题。
提前致谢！
您可以使用广度优先搜索。对于每个顶点，跟踪：
- 从u到那个顶点的最短路径长度
- 每当你处理一个给定的顶点时，你都会为它的所有尚未设置此 属性 设置的邻居设置此 属性。
- 这兼作 "has already been enqueued" 标志：您最初设置为标记值，例如 ɴɪʟ 或 ∞，并且只为任何给定的顶点更新一次。所以你不需要一个单独的标志来跟踪访问过的顶点。
- 从u到该顶点的最短路径数
- 每当你处理一个给定的顶点时，你都会为它的所有邻居适当地增加这个 属性，这些邻居从 u 的最短路径长度大于你的顶点'正在处理中。
- 请注意，您将针对某些顶点多次更新此 属性，但这没关系，因为您只为每条边更新一次。
当给定一个有顶点和边的图 G |V|和|E|分别和顶点u和t，写一个O(|E|+|V|)算法来计算从u到t的最短路径的数量，即如果有5条长度为4的路径，其中长度4是从u的最短路径到 t 那么算法将输出 5.
我知道该算法必须以某种方式包含 DFS 或 BFS，因为它的 运行-time 因为每个算法都有 O(|E|+|V|) 运行-time ，但我有点卡住了。我尝试实现一些东西，它会重复执行 DFS，算法在 t 处终止，但这对于决定将哪些节点设置为已访问以及在每次迭代后将哪些节点重置成为问题。
提前致谢！
您可以使用广度优先搜索。对于每个顶点，跟踪：
- 从u到那个顶点的最短路径长度
- 每当你处理一个给定的顶点时，你都会为它的所有尚未设置此 属性 设置的邻居设置此 属性。
- 这兼作 "has already been enqueued" 标志：您最初设置为标记值，例如 ɴɪʟ 或 ∞，并且只为任何给定的顶点更新一次。所以你不需要一个单独的标志来跟踪访问过的顶点。
- 从u到该顶点的最短路径数
- 每当你处理一个给定的顶点时，你都会为它的所有邻居适当地增加这个 属性，这些邻居从 u 的最短路径长度大于你的顶点'正在处理中。
- 请注意，您将针对某些顶点多次更新此 属性，但这没关系，因为您只为每条边更新一次。