给定具有顶点和边| V |的图G时和| E |分别和顶点u和t,写一个O(| E | + | V |)算法来计算从u到t的最短路径的数量,即如果有5条长度为4的路径,长度为4的路径是来自u的最短路径然后算法将输出5。
我知道算法必须以某种方式包含DFS或BFS,因为它的运行时间因为每个都有O(| E | + | V |)运行时,但我有点卡住了。我尝试实现一些东西,它会在算法终止于t的情况下反复执行DFS,但这对于决定将哪些节点设置为已访问以及在每次迭代后要重置哪些节点会产生问题。
提前致谢!
您可以使用广度优先搜索。对于每个顶点,请跟踪: