算法 - 通过特定顶点的路径查找

Question

我正在寻找一种方法来找到从源顶点 (S) 到经过某处另一个特定顶点 (X) 的目标顶点 (D) 的无环路径（最好是最短路径，但不一定）在图中。

现在，在你指出我之前我想说这个解决方案忽略了从 S 到 X 的最短路径已经包括 D 的情况，这是我应用这个算法的可能场景。在那种情况下你会如何解决这个问题？

我尝试的是在 Yen 的 K 最短路径算法的结果中寻找这样的路径的幼稚尝试。但我希望有一种更有效和更确定的方法来做到这一点。

再次指出，我不一定要寻找从 S 到 D 通过 X 的最短路径，而是寻找任何无环路径，尽管最短路径会更好。

Answer 1

基本概念很简单；然后你就可以适应在最短剩余路径上循环进出 X 的情况。

从图中删除 D。
求P1，从S到X的最短路径。
将 D 恢复到图形。
删除 P1 中的所有节点。
求P2，从X到D的最短路径。
return P1 + P2.

这就是解决方案的要点。

注意：您可能会发现删除 P1 会产生一个子图，其中没有到 D 的剩余路径。在这种情况下，您将需要一个动态规划解决方案搜索上面的想法，但使用回溯和另一种方法来搜索 P1 候选人。

当您第一次找到 P1 时，请检查您将要使用的节点不会在行程的第二段将 X 与 D 隔离。这将为您提供更快的搜索算法。

开始就够了吗？

适应的需要来自这样一个案例—— 考虑图表

src  dst
 S    1, 2
 1    X, D
 2    D
 X    1

您的部分路径是

S -> 1 -> X
S -> 2 -> 3 -> X
X -> 1 -> D
and, incidentally,
S -> 1 -> D

当您运行搜索最短路径时，您会得到路径 S 1 X 1 D，因为循环而被拒绝。当您实施我的第一个修改时——在尝试查找路径 X to D 时删除节点 1，没有剩余路径。

算法需要备份能力，拒绝路径X 1 D寻找X 2 3 D。这是从描述中不能立即看出的编码。

给你一个脑力练习：是否可以构造一个图，其中每条最短路径（S to X 和 X to D）将另一个隔离开来来自 X 的终端节点？在我上面的示例中，您可以简单地切换过程：当 S to X 路径隔离 D 时，然后重新开始：首先找到 X to D，删除节点 1，然后然后在剩下的图中找到S to X。你能找到这个开关不起作用的图表吗？

如果没有，您有一个即时的解决方案。如果是这样，您需要处理更复杂的情况。

算法 - 通过特定顶点的路径查找

algorithm - Path finding through a specific vertex

python

algorithm

graph-theory

dijkstra

path-finding