问题标签 [max-flow]

我有一个带有一些边和节点的流网络。在离开该源节点的边上，我想放置一些最小流量，以便在该边上至少有 x 流量（如果这不可能，我想知道这一点）。我已经实现了 Ford-Fulkerson 算法来找到最大流量，但我不确定如何调整我的算法来做到这一点。我考虑过减少离开源节点的边缘的容量，但这对我不起作用。

谁能指导我解决这个问题的正确方向？

提前致谢！

对于最大流量问题，似乎有许多非常复杂的算法，至少有一种算法是在去年才开发出来的。Orlin 的Max 在 O(mn) 时间或更短的时间内流动，给出了在 O(VE) 中运行的算法。

另一方面，我最常看到实现的算法是（我并没有声称已经进行了详尽的搜索；这只是偶然的观察）：

• 埃德蒙兹-卡普，O(VE^2)
• Push-relabel, O(V^2 E), or O(V^3) 使用 FIFO 顶点选择
• Dinic 算法，O(V^2 E)

具有更好渐近运行时间的算法对于现实世界中的问题规模是否不实用？另外，我看到很多算法都涉及“动态树”；这些曾经在实践中使用过吗？

我对 Ford-Fulkerson 算法的分析不正确。例如，请看下图：

节点 0 是源节点，节点 6 是终端节点，每条边的限制都是 1，除了节点 0 到 1 的边的限制是 2。如果流从 0->1->3->6 和 0- >1->4->6 和 0->2->5->6，图形的流向是 3。但是，如果流从 0->1 开始，则选择从 0->1->3 开始->6 和 0->1->5->6，我们不能再从 0->2->5->6 走，因为 5->6 已经被占用了。由于 0->1 的限制是 2，所以我们只能从 0->1 开始两次，因此，图的流量是 2。显然，图的最大可能流量应该是 3 而不是 2。请问 Ford-Fulkerson算法处理这个问题并总是返回 3 作为答案？

我正在阅读维基百科上的最大流量问题。我很好奇问题描述是否允许 s 等于 t （源等于接收器）。我知道如果 s =t ，答案必须是 0。但是，假设我正在编写代码来解决这个问题。我的代码应该处理这种特殊情况还是问题描述禁止这样做。

你好美妙的社区！

我目前在业余时间写一个小游戏。它发生在一个大星系中，玩家可以控制一些星星。在这些星星上，您可以构建Buildings，每个建筑物都有一定数量（0..*）的输入，并产生一定数量的输出。这些建筑物具有最大容量/吞吐量，并且按比例缩小其输入会按比例缩小其输出。我想找到一种预算算法来优化（或近似）所有建筑物的吞吐量。这似乎是某种最大流量问题，但我读过的流量优化算法都没有不同类型的输入或依赖输出。

我一直在玩的玩具“科技树”是：

我愿意接受次优算法，并且我愿意保证输入/输出没有循环（它们从构建到构建形成 DAG）。这个想法是在没有玩家干预的情况下允许合理的吞吐量和科技树复杂性，因为在数百或数千颗星的规模上，允许玩家手动定义预算策略并不有趣，并且给没有生命的玩家一个独特的优势。

我目前的策略是建立一个有向无环图，给资源一个总排序（船比金属好比矿石比能源好），然后，循环遍历每个资源，找到最“后代”的建筑生产该资源，让它递归地贪婪地从其输入中获取（造船厂将需要 2 能量和 1 金属，然后精炼厂将获取 1 能量和 1 矿石等），然后在图表中找到任何“骗子”（太阳能发电厂提供 4 种能量，最大值为 2 种），缩减其生产并向前传播变化。为 DAG 解决所有问题后，从图中删除终端元素（造船厂），并从建筑物的最大吞吐量中减去每条边的“当前吞吐量”，然后对下一种资源重复该过程。我想如果有更好的方法，我会问比我聪明得多的人。:)

让 G = (V, E) 是一个网络，其中 s 和 t 是源和汇。设 f 是 G 中的最大流。找到一个算法来确定 G 中是否存在唯一的最小割。

我设法在这个网站上找到了一个类似的问题：

确定最小切割的唯一性

那里给出的答案摘要：

在残差图中找到从 s 可达的所有顶点，我们在 G 中找到了一个最小割 (S,T)。

查看相同的残差图，从 t 开始。以箭头的相反方向查看从 t 可到达的顶点组（表示可以到达 t 的所有顶点）。

这组也是最小切。

如果该剪辑与您的原始剪辑相同，则只有一个。否则，您只找到了 2 个剪辑，所以原来的剪辑不可能是唯一的。

我不明白为什么如果剪辑与原始剪辑相同，那么剪辑就是独一无二的。谁能向我们保证没有其他最小切割？

提前致谢

如果我想在无向图中找到最大流量，我该怎么做？

在维基百科页面http://en.wikipedia.org/wiki/Maximum_flow_problem它说算法需要有向图（我只是将每条边转换为一对边）但问题是我可能有非整数权重（例如0.5)。

有没有适合这个问题的现有算法？

我正在使用 python igraph 的 all_st_mincuts 函数来切割具有约 3000 个顶点和约 9000 个边的非平面双向图。根据我分配给边缘的容量，有时 all_st_mincuts 返回 0 个切割！在我看来，图表不可能没有最小 st 削减。什么可能导致这种行为？

我正在使用 matlab 内置的最大流算法来处理无向图。每条边都被两个具有相同容量 1 的有向边替换。但是，它遇到了一个错误：“最大流算法中不允许倒数边”。matlab内置最大流算法是否支持无向图？

假设我在图 G = (V,E) 上运行了 Ford-Fulkerson 算法，结果是一个 max-flow f _max，它与一个 min-cut Xmin 相关联。我有兴趣通过增加图中任何一条边的容量来尽可能地增加流量。我怎样才能识别这个边缘？

一种策略可能是：给定初始顶点s和最终顶点t ，考虑从s到t的所有路径并验证容量较低的边。例如，如果我有一个 1/1 的边，这是我必须增加容量的顶点。

有解决这个问题的通用算法吗？