如何求一个带权无向图中包含两个给定节点的最小带权圈？
给定一个加权无向图G=(V,E)和一组节点P。
给定两个节点n1和n2。
我想找到从n1到n2的两条单独的（不重叠的）路径，使两条路径的权重之和最小。我将这个问题解释为标题所描述的，即包含n1和n2的最小加权循环。
显然，从n1到n2找到第一条最小加权路径p1然后从图中去掉p1中的边，然后找到第二条最小加权路径p2是不正确的。
我怎么才能找到这样的循环呢？
共有1个答案
这个问题可以用流动网络来解决。参见Edmonds-Karp算法：它包括在每一步计算增广路径。
像Edmonds-Karp算法中描述的那样，使用广度优先搜索（如果您的图是加权的，请使用Bellman-Ford）找到一条增广路径。
然后，以同样的方式找到另一条增广路径。消除在两条路径中出现的边缘（流算法实际上会替你照顾这一点），那将是你的循环。基本上，如果您将所有边都设置为capacity1，您的循环将由您推过1流的边组成。
如果你不喜欢基于流的解决方案，这里有另一个。基本上是一样的，只是在流量算法方面不一样。
>
用任何能做到这一点的算法找到最短路径n1->n2（如果没有负代价，则为Dijkstra，否则为Bellman-Ford）；
用从n2指向n1的有向弧替换此最短路径的边。例如，如果最短路径为n1->x->y->z->n2，则将边(n1,x)替换为有向弧x->n1，将边(x,y)替换为有向弧y->x等。
也可以抵消这些弧线的成本。例如，如果(x,y)具有成本C，则有向弧Y->x将具有成本-C。
在此新图形中查找从n1到n2的最短路径。现在你必须使用一个能处理负边的算法。
删除出现在两条最短路径中的边。你剩下的就是你所追求的循环。
-
我有一个有向加权图
-
我需要帮助在一个未加权无向图中找到两个节点之间的所有最短路径。 我能够使用BFS找到一条最短路径，但到目前为止，我还不知道如何找到并打印出所有路径。 知道我可以使用的算法/伪代码吗？
-
总结 因此，我有一个有向无环加权图，其中每条边都有一个输入和输出节点，每个节点都有一个ID，我使用一个字典将所有传入的边映射到一个节点的ID，并使用另一个字典对所有传出的边进行同样的操作，这样，当出现节点ID时，我可以在大约O(1)时间内告诉所有传入和传出的边。 要求 我需要能够添加新的随机边(即连接两个随机节点)，以保证无论图有多大，它都不会有任何循环。 我试过的 由于我完全控制如何构建我的图，
-
路径的“length”是路径中的边数。 给定一个源和一个目的顶点，我想求出给定长度k的从源顶点到目的顶点的路径数。 > 我们可以任意多次访问每个顶点，因此，如果从到的路径如下:被认为是有效的。这意味着可以有循环，我们可以通过目的地不止一次。 由于答案可能很大，所以要以模的形式报告。 以下是我到目前为止的想法： 我们可以使用广度优先搜索而不将任何顶点标记为已访问的，在每次迭代中，我们跟踪该路径所需的
-
我有一个无向加权图，我需要找到分隔两组顶点的最小切口。我可以修改我的设置，以便将问题减少到找到分隔两个给定顶点的最小切口。我想补充的是，权重是正数和分数。 Stoer–Wagner算法除了将指定的节点保留在切割的不同侧面之外，什么都可以做，我很好奇是否有办法修改SW来做到这一点。 非常感谢。
-
以下是消费税： 在某些图的问题中，顶点可以有权代替边的权或增加边的权。设Cv是顶点v的代价，C(x，y)是边(x，y)的代价。该问题涉及到在图G中寻找顶点a和顶点b之间的最便宜路径，路径的代价是该路径上遇到的边和顶点的代价之和。 (a)假设图中每条边的权重为零（而非边的代价为∞)，假设所有顶点1≤V≤n（即所有顶点的代价相同），Cv=1。给出一个求从a到b最便宜路径的高效算法及其时间复杂度。 (b