algorithm - 如何在加权（无向）图中找到两个节点之间长度为 X 的路径

Question

给定一个图，如何在图中的两个节点之间找到长度为 X 的路径。理想情况下，路径应该不超过一次访问边缘。

Answer 1

您可以实现修改后的 BFS 算法。一旦你找到从 A 到 B 的第一条路径，你就有了这条路径的最小长度，所以如果 X 小于这个值，你就已经知道现在有路径了。

如果 X 大于此值，请按以下方式进行：遍历刚刚找到的从 A 到 B 的路径，并用它到 B 的距离来注释每个节点。

然后，继续您的 BFS 搜索，直到您覆盖整个图表。

每次你的搜索到达一个已经使用过的节点时，你可以查看它是否通向 B，如果是，离它有多远。这可以让你知道刚刚找到的新路径的长度，并且可以与 X 进行比较。

再次，用它与 B 的距离来注释此路径中的每个节点。您应该允许对节点进行多次注释，并且一旦您遇到通向 B 的已使用节点，请使用所述节点的所有注释值进行比较。

每当您遇到长度大于 X 的路径时，您都可以停止搜索。