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

Question

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

Answer 1

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

如果X比这个值大，就像这样进行：检查你刚刚找到的从A到B的路径，并用它到B的距离注释每个节点。

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

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

同样，用它到B的距离来注释这条路径中的每个节点。你应该允许一个节点被注释多次，一旦你遇到了一个通向B的使用过的节点，就使用该节点的所有注释值进行比较。

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