标签: network-flow

在谈到时computing network flows,算法设计手册说:

传统的网络流算法基于增加路径的想法,并重复地从s到t找到正容量的路径并将其添加到流中.可以证明,当且仅当它不包含增广路径时,通过网络的流是最佳的.

我不明白是什么augmenting paths.我用Google搜索,发现:

• 增强Wolfram的路径

• Wiki中的流网络

但他们都参考了上面的引用.

任何人都可以真的清楚地解释一下是augmenting path什么？

我正在解决一个优化问题,其中,我必须最大化流网络.我实现了一个基于c ++代码的流量最大化算法,该算法基于以下java代码,该代码出现在Sedgewick"Java中的算法,第三版,第5部分:图算法"一书中,它使用基于顶点的PREFLOW最大化网络流量 -推算法:

class NetworkMaxFlow
{ private Network G; private int s, t;
  private int[] h, wt;
  private void initheights()
  NetworkMaxFlow(Network G, int s, int t)
  { this.G = G; this.s = s; this.t = t;
    wt = new int[G.V()]; h = new int[G.V()];
    initheights();
    intGQ gQ = new intGQ(G.V());
    gQ.put(s); wt[t] = -(wt[s] = Edge.M*G.V());
    while (!gQ.empty())
    { int v = gQ.get();
      AdjList A = G.getAdjList(v);
      for (Edge e = A.beg(); !A.end(); e = A.nxt()) …

给定有向加权图,如何在所有顶点对之间找到最大流量(或最小边缘切割).
天真的方法就是调用像Dinic这样的Max Flow算法,其复杂度O((V^2)*E)为每对.
因此对于所有对都是如此O((V^4)*E).

是否有可能降低复杂性,O((V^3)*E)或O(V^3)通过一些优化？

我应该使用什么算法来查找有向下限但不是上限的有向图上的最小流量？比如这个简单的例子:

在文献中,这是最小的成本流问题.然而,在我的情况下,成本与每个边缘所需流量的非零下限相同,所以我在上面提出问题.在文献中,问题是:找到单源/单宿有向无环图的最小成本流的最佳算法是什么,其中每个边具有无限容量,流上的非零下界,以及成本等于流量的下限.

根据我的研究,似乎人们处理任何类型网络的任何类型的最低成本的主要方式是将问题设置为LP类型问题并以此方式解决.然而,我的直觉是没有流动的上限,即具有无限容量的边缘,使问题更容易,所以我想知道是否有一种算法专门针对这种情况使用比单纯形法等更多的"图形"技术. .人.

我的意思是,如果所有的成本和下限都是1,如上所述...我们正在寻找一个涵盖所有边缘的流程,遵守流程规则,并且不会在从s到t的任何路径上推动太多流量.这只是感觉它不应该要求LP求解器,事实上维基百科关于最小成本流的文章指出"如果容量约束被移除,问题就会减少到最短路径问题"但我认为他们正在讨论下限全部为零的情况.

还有开源C/C++代码,可以在任何地方实现最低成本流量吗？从谷歌搜索可用的东西,我发现我可以自己设置问题作为LP问题,并用开源LP解算器解决,或者我可以使用LEMON,它为最低成本流提供了几种算法.据我所知,boost图库不包含实现.

还有别的事吗？

有人可以帮我解决这个问题吗？解决方案显然是使用网络流量,但我不是很熟悉网络流量.网络流程如何帮助您解决这个问题？

螃蟹是一个无向图,它有两种顶点:1个头和K个脚,正好是K个边缘,它们将头部连接到每个腿上.(1 <= K <= T,其中给出了T)

给定一个无向图,你必须在其中找到一些顶点不相交的子图,其中每个子图都是一个螃蟹.目标是以这样的方式选择那些螃蟹,使得它们所覆盖的顶点的总数最大化.

注意:如果两个图形没有任何共同的顶点,则它们是顶点不相交的.

例如 输入

8 2 7
1 4
2 4
3 4
5 4
5 8
5 7
5 6

我试图解决有关最大流量问题的问题.我有一个源和两个接收器.我需要在这个网络中找到最大流量.这部分是一般的最大流量.但是,这两个目标必须在此特殊版本的最大流量问题中获得相同的流量.

是否有人可以帮助我,我该怎么做呢？

我有一个边加权无向图和 2 个节点（通常称为源和汇）。我需要找到一组最小可能权重的边，它将这 2 个节点分成 2 个弱组件。

我知道Ford-Fulkerson的最大流算法以及他的最大流和最小割关系定理以及他关于有向图上的

我还知道福特-富尔克森无向图最大流算法的修改，它将每个无向边替换为 2 个相反的有向边，并同时更新它们的流。但经过此修改，最大流最小割定理似乎不再有效，因为在以下无向图上，将无法正确确定最小割：

nodes: 0, 1, 2, 3\nedges & capacities: {0,1}->5, {0,2}->6, {1,2}->2, {1,3}->7, {2,3}->4\nsource: 0\nsink: 3\n

最大流最小割定理说，最小割是那些流量等于其容量的边，而根据修改后的福特-富尔克森，这是所有边，这显然不是正确的割。

我找到了一个Stoer\xe2\x80\x93Wagner 算法，用于在无向图中查找全局最小割，但这不是我想要的，因为该算法不考虑任何源和汇，并且可以找到一个cut，这让节点位于同一个组件中。

是否有任何算法可以有效地在具有源和接收器的无向图中找到最小切割，将这两个指定的节点分开？\n我可以以某种方式修改前面提到的算法以使它们适用于我的情况吗？

我无法理解如何在具有下限（不是需求）的网络中找到循环流。我找到了下一个包含问题描述和解决策略的文档：

1. https://www.cs.cmu.edu/~ckingsf/bioinfo-lectures/flowext.pdf
2. http://homes.cs.washington.edu/~anderson/iucee/Slides_421_06/Lecture24_25_26.pdf
3. http://web.engr.illinois.edu/~jeffe/teaching/algorithms/2009/notes/18-maxflowext.pdf

让我们考虑一个具有以下边的网络（l - 下限，c - 容量）：

1 -> 2 : l = 1 c = 3

2 -> 3 : l = 2 c = 4

3 -> 1 : l = 1 c = 2

据我了解，要解决这个问题，我们应该采取以下步骤：

1. 把这个问题转化为“有需求的流通问题”。这可以通过下一个公式 dv' = dv - (Lin - Lout) 来完成，其中 'dv' 是原始顶点需求（在我们的例子中它等于 0），'Lin' - 顶点输入边下界的总和，以及 ' Lout' - 顶点输出边下界的总和。
2. 将边容量更新为 c' = c - l
3. 将带有边的源顶点 S 添加到 dv < 0 且容量为“-dv”的每个顶点
4. 添加接收器顶点 T 和每个顶点的边，dv > 0，容量为“dv”
5. 使用任何算法（例如 Edmonds-Karp 算法）在新网络中找到最大流量。
6. 如果最大流的值等于与 …

据我了解，Ford-Fulkerson 算法可以找到流量网络中可以从源 ( s) 流向汇 ( )的最大流量。 但是是否有一种算法可以找到给出最大流量的所有可能的路径集？t

举个例子：
在下面的这个网络中，所有边的容量都是 1。不难看出，从s到 的最大流量t是 3。但是如何找到承载该流量的路径组合呢？

预期输出：
路径集 1：s-0-1-t, s-2-3-t, s-5-6-t
路径集 2：s-0-1-t, s-2-4-t, s-5-6-t
路径集 3：s-0-3-t, s-2-4-t, s-5-6-t
路径集 4：s-0-4-t, s-2-3-t, s-5-6-t

这里提出了类似的问题，但似乎没有得到明确的答案。

我想将 Dinic 算法应用于动态树。但我找到的来源很少。特别是关于动态树。如果有详细解释的好的源代码或一些使用动态树的简单源代码，那就太好了。

有没有人遇到过这样的事情？提前致谢