问题标签 [max-flow]

我正在尝试使用从源节点 s 到目标节点 t 的最大流量来查找k（给定 k）路径，并在图 G =（V，E）中具有一些约束。给定 V 的不同子集 A_i，一个子集可以有一个或多个节点。问题是我只能在一个路径中使用一个子集。我正在使用此代码查找最大流量

如何添加每个子集只能在此代码中使用一个路径（我的意思是，如果我在路径 1 中使用子集 A_1，那么我不能再将 A_1 用于其他路径？我是 java 新手。我试图上传我的问题图片，但我不能，因为我是这方面的新手。谢谢

有没有办法在matlab中找到每对顶点之间的最大流量？

或者

因此，我可以采用稀疏矩阵并获得从一个顶点到所有其他顶点的最大流量。有没有办法继续这个以获得所有对的最大流量？

我最终希望能够找到有向加权图的所有对最大流量。. .

我一直在尝试理解这段代码；它是 C++ 中 push-relabel 算法的实现：

代码可以编译并且可以工作，但我不明白我应该如何将输入传递给它。理想情况下，一个main()函数应该读取源和接收器（无论如何它们都是“虚构的”，并且只是算法工作所必需的），然后是构建图形所需的所有数据AddEdge()。但是如何做到这一点目前超出了我的范围。

我的main()应该是这样的

我认为这source应该用于初始化 some Edge.froms，它应该与sinkand some Edge.tos 类似，但我不知道如何构建图形。

我一直在尝试自学一些简单的计算机视觉算法，并试图解决一个问题，其中我有一些噪声损坏的图像，而我所要做的就是将黑色背景与有一些信号的前景分开。现在，背景 RGB 通道并非完全为零，因为它们可能有一些噪声。然而，人眼可以很容易地从背景中辨别出前景。

所以，我所做的是使用 SLIC 算法将图像分解为超像素。这个想法是，由于图像被噪声破坏，对补丁进行统计可能会因为更高的 SNR 而对背景和前景进行更好的分类。

在此之后，我得到了大约 100 个应该具有相似配置文件的补丁，并且 SLIC 的结果似乎是合理的。我一直在阅读有关图形切割的文章（Kolmogorov 论文），尝试解决我遇到的二元问题似乎很不错。因此，我构建了一个图，它是一阶 MRF，并且在直接邻居之间有边（4 连通图）。

现在，我想知道我可以在这里使用哪些可能的一元和二元术语来进行分割。所以，我在考虑一元项，我可以将它建模为一个简单的高斯，其中背景应该具有零均值强度，而前景应该具有一些非零均值。虽然，我正在努力弄清楚如何对其进行编码。我应该假设一些噪声方差并直接使用补丁统计信息计算概率吗？

同样，对于相邻的补丁，我确实想鼓励他们使用类似的标签，但我不确定我可以设计什么二进制术语来反映这一点。似乎只是标签（1或0）之间的区别似乎很奇怪......

很抱歉这个冗长的问题。希望有人可以就如何开始提供一些有用的提示。

我想在我的项目中对图像使用图形切割算法，我使用的是python 2.7。
我找到了pymaxflow implementation，但文档似乎不太清楚。我举个例子，这是我的 5*5 矩阵：

虚拟终端节点S（源）和T（汇）应分别与矩阵最左侧和最右侧列的所有像素用无限权弧连接。这是我想要获得的：

这是我获取此代码的代码，但它不起作用

g.maxflow()使 python 控制台处于无限循环中。我不确定我的实现：制作可用于图形切割算法的正确图形的方法是什么？

谢谢！

Ps 如果您知道另一个库的解决方案，请告诉我，任何建议将不胜感激。

我认为这就像最大流问题的无向图版本。

所以对于每条边 a->b，b->a 也是有效的。它的双向。他们共享相同的容量。这意味着如果我在两个顶点 a、b 之间的容量为 10，并且我有从 a 到 b 的流量为 5，那么从 a 到 b 的剩余容量以及从 b 到 a 的剩余容量将是 5。

我对此的解决方案是有一个从 b 到 a 的有向边和另一个从 a 到 b 的有向边。问题是，如果我在残差图中从 a->b 减少残差，我是否仍会增加后向边 b->a 的残差？

I implemented first phase of the highest label push relabel algorithm for maximum flow but I could not find any resources about how to implement the second phase, i.e. to convert the preflow push network to a valid flow network.

这是给你的算法挑战，

我有一个[0..100]数字对列表，我需要找到唯一“左数”的最大数量，同时确保“右数”不超过 3个。

这是一个例子

• (1, 1)
• (2, 1)
• (3, 1)
• (4, 1)
• (5, 1)
• (6, 1)
• (7, 1)
• (1, 2)
• (4, 2)
• (1, 3)
• (2, 3)
• (5, 4)

结果将是：7。我们将采用：(3, 1), (6, 1), (7, 1), (1, 2), (4, 2),(2, 3)和(5, 4)。

无论出于何种原因，我似乎找不到任何其他方法，而不是蛮力强迫它......

任何帮助是极大的赞赏 ：）

我使用 edmonds-karp 实现编写了一个 Max-Flow 类。当我尝试获取最大流量的值时，代码似乎可以正常工作。我在 SPOJ TotalFlow上提交了代码，所以我相信实现是正确的。

但我试图从残差图中得到 Min-Cut。这导致了一些错误。任何帮助都会很有用。

我的主要功能如下

考虑我们有一个网络流量，并且使用 Edmond-Karp 算法，我们已经有了网络上的最大流量。现在，如果我们向网络添加任意边（具有一定容量），那么更新最大流量的最佳方法是什么？我正在考虑更新关于新边缘的残差网络并再次寻找增强路径，直到我们找到新的最大流量，但我不确定它是否有效或者它是否是最好的方法！