查找覆盖两个节点之间所有边的路径
我们希望您能够帮助我们解决以下问题：
给出了一个可能包含圈的有向图。必须找到一组满足以下标准的路径：
在从节点A到节点B的过程中可以通过的所有边必须被集合内的路径覆盖（一条边可以是集合中多条路径的一部分）
解决方案不必是路径数最少的解决方案，路径也不必是最短的。然而，该解决方案应该可以像java一样使用编程语言高效地实现。我们需要解决方案来生成几个测试用例，覆盖节点a和节点B之间的所有边很重要。
每个人都知道合适的算法吗？还是没有有效的解决方案？
非常感谢您的建议！（我们已经搜索了一个解决方案，但我们找到的那个专注于最短路径，效率极低）
以下是我们问题的图形表示：
http://i.stack.imgur.com/wIY34.jpg
共有1个答案
考虑所有可从A到达的边R（A）。可以通过在每条边上添加一个节点（即将每条边转动U）来找到这些边-
很明显，R（A）之外的边不能位于从A到B的路径上，因为从A到B的路径是可以到达的。所以到B的所有路径都必须穿过R（A）的边。
因此，我们想要“覆盖”的边集U是R（A）的所有边，B可以从这些边到达。
现在我们正在寻找一组从A到B的路径S，其中包含U的所有边。
一个简单的方法如下：
- 将R（A）的所有边缘涂成黑色并设置S={}
- 当黑边剩余时：
- UV黑边。
- 如果B可从V到达：
- 构造路径P=A-
- 将UV颜色设置为灰色
正如@user189所指出的，如果我们考虑从A到B的可达边，我们允许通过B两次的路径（即a-
关于复杂性：
R（A）可以在O（|E|）时间内计算，从A到R（A）中的边缘UV的路径可以直接从BFS树中读取。为了检查从V到B的可达性并找到路径，我们可以使用从B开始并向后跟随边缘的BFS树，在O（|E|）时间内计算。
如果我们通过连接两个BFS树的边UV隐式引用路径，并使用O（1）读取/更新结构来维护黑色边集并在BFS树中查找边，我认为我们可以在O（| E |）时间内完成此操作。
-
问题内容： 我正在使用networkx处理图。我有一个很大的图（其中有近200个节点），我尝试查找两个节点之间的所有可能路径。但是，据我了解，networkx只能找到最短的路径。如何不仅获得最短路径，还获得所有可能路径？ UPD：路径只能包含每个节点一次。 UPD2：我需要类似find_all_paths（）函数的功能，在此进行描述：python.org/doc/essays/graphs.htm
-
我试图通过在MST中添加新顶点来更新MST。为此，我一直在关注Chin和Houck的“更新生成树”。http://www.computingscience.nl/docs/vakken/al/WerkC/UpdatingSpanningTrees.pdf 论文中的一个步骤要求我在两个给定顶点之间的路径中找到最大的边。我的想法是找到顶点之间所有可能的路径，然后从这些路径中找到最大的边。我一直在尝试在
-
我有一个有向加权图G，其中权重是过渡的持续时间。 我使用DFS编写了两个顶点之间的所有路径搜索算法，并进行了修改：搜索将继续，直到路径的总权重（其各部分的权重之和）小于某个值。 我的代码在小图中工作，但在大图中（| V |=1800，| E |=50870）它会冻结。
-
这应该是正确的：
-
我有一个有向图。我想找到从源到目标的所有可能路径，覆盖所有转换。这与“覆盖所有顶点的所有可能路径”不同。该图将正好有一个起始顶点，并且可能有多个结束顶点。如果没有传出转换，则节点是结束节点。集合中的路径可能具有重复的变换，但不能具有重复的顶点。附有一个示例有向图。顶点a（黑色）是起始顶点，顶点e和f是结束节点（黄色）。此图的解决方案如下所示。 您可以看到最后一条路径有两次b。这是有效的。i、 例如
-
王国连通性 对查尔斯国王来说，这是繁荣的一年，他正在迅速扩大他的王国。一个美丽的新王国最近已经建成，在这个王国里有许多城市由多条单向道路连接。两个城市可能由多条道路直接连接，这是为了确保高度连接。 在这个新王国中，查尔斯国王将其中一个城市作为他的金融首都，另一个作为战争首都，他希望这两个首都之间有高度的连通性。一对城市的连通性，比如城市A和城市B，被定义为从城市A到城市B的不同路径的数量。如果可能