未加权图中的路径：从源头到源头的最短行程，强加一个点

Question

在我的未加权图中，我需要从源顶点到达强加的顶点并返回源。 所有顶点最多只能被访问一次。 （该图中可能存在循环。） 我想要最短路径的长度。

寻找“快速”算法：

我已经在Python中进行了多次尝试，但速度不够快。 ;-) 最新的例子：从源到强加点的所有路径的生成器（按长度增加的顺序），每次我得到一条新路径时，将其与所有已经计算的路径进行比较，如果不相交则停止。 结果很好，但太慢/内存昂贵。 早些时候（同一问题）：考虑带有信息的子状态：位置、是否已经到达强加的点、已访问的顶点集...结果也很好，但太慢/内存昂贵。

欢迎使用DP解决方案。

用谷歌找不到东西。如果你知道哪里有东西，请指点我。

谢谢。

--- 示例 ---

e...
#!!#
#!.#
...s

这是一个迷宫；你从“e”进入，需要到达剑的“s”并返回入口“e”。 '#' 是无法通过的。 '！'是陷阱，当你走在这些陷阱上时，你会触发它们并且无法再次通过。 在本例中，我已将其转换为具有 5 个顶点的图：e,s, (2,2), (3,2) 和 (2,3)

--- Suurballe 算法产生两条不相交路径的情况 ----

.....
##!!#
#!!!#
#!!##
.....

Answer 1

对于未加权图，两个方向的最短路径 BFS 可能是最有效的解决方案。

您可以使用 BFS 来确定每个节点距源的距离。

找到路径后，您可以删除源和目标旁边的每个节点，这样您就不会多次重复路径上的节点，然后使用 BFS 从目标返回到源。

总复杂度是线性的 O(V+E)

更多相关内容： https://www.geeksforgeeks.org/shortest-path-unweighted-graph/

Answer 2

如果我正确理解你的问题，那么我认为你正在寻找的是节点不相交路径。发现它们的经典算法是由Suuballe提出的。另一种基于网络流的算法在networkx中实现：networkx.algorithms.connectivity.disjoint_paths.node_disjoint_paths.

希望这些指针能够以足够的速度解决您的图表中的问题。