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

问题描述 投票:0回答:1

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

我知道算法必须以某种方式包含DFS或BFS,因为它的运行时间因为每个都有O(| E | + | V |)运行时,但我有点卡住了。我尝试实现一些东西,它会在算法终止于t的情况下反复执行DFS,但这对于决定将哪些节点设置为已访问以及在每次迭代后要重置哪些节点会产生问题。

提前致谢!

algorithm graph-theory depth-first-search breadth-first-search
1个回答
1
投票

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

  • 从u到该顶点的最短路径长度 无论何时处理给定顶点,都要为尚未设置此属性的所有邻居设置此属性。 这也是“已经入队”标志的两倍:您最初设置为sent或∞等标记值,并且只对任何给定顶点更新一次。因此,您不需要单独的标记来跟踪访问的顶点。
  • 从u到该顶点的最短路径数 无论何时处理给定的顶点,都要适当地为其所有邻居增加此属性,这些邻居的最短路径长度大于您正在处理的顶点的路径长度。 请注意,对于某些顶点,您将多次更新此属性,但这没关系,因为每个边缘只更新一次。
© www.soinside.com 2019 - 2024. All rights reserved.