python - algorithm - 通过特定顶点的路径查找

Question

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

现在，在你指出我 找到通过特定顶点之间的最短路径之前，我想说这个解决方案忽略了从 S 到 X 的最短路径已经包括 D 的情况，这是我应用这个算法的可能场景. 在这种情况下，您将如何解决这个问题？

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

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

标签： pythonalgorithmgraph-theorydijkstrapath-finding

Answer 1

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

• D从图中删除。
• 求，从到P1的最短路径。SX
• 恢复D到图表。
• 删除P1.
• 求，从到P2的最短路径。XD
• 返回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

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

该算法需要能够备份，拒绝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在剩余图中查找。你能找到这个开关不起作用的图表吗？

如果没有，你有一个直接的解决方案。如果是这样，你有一个更复杂的情况要处理。