标签: ford-fulkerson

为了找到图中的最大流量,为什么不仅仅考虑该路径中具有最小边缘容量的所有增强路径而不考虑后边缘就足够了？我的意思是,如果我们从它那里假设流量,那么称它为后沿是什么意思呢？

我正在尝试使用Ford-Fulkerson算法解决图的最大流问题.该算法仅用有向图描述.当图表无向时怎么办？

我模仿无向图的方法是在一对顶点之间使用两个有向边.令我困惑的是:这些边缘中的每一个是否应该有剩余边缘,或者是剩余边缘的"相对"有向边缘？

我假设了最后一个,但我的算法似乎进入了无限循环.我希望你们中的任何人能给我一些帮助.以下是我自己的实现.我正在使用DFS查找.

import sys
import fileinput

class Vertex(object):
    def __init__(self, name):
        self.name = name
        self.edges = []

    def find(self, sink, path):
        if(self == sink):
            return path
        for edge in self.edges:
            residual = edge.capacity - edge.flow
            if(residual > 0 or edge.inf):
                if(edge not in path and edge.oppositeEdge not in path):
                    toVertex = edge.toVertex
                    path.append(edge)
                    result = toVertex.find(sink, path)
                    if result != None:
                        return result

class Edge(object):
    def __init__(self, fromVertex, toVertex, capacity):
        self.fromVertex = fromVertex
        self.toVertex = toVertex
        self.capacity = capacity …

我正在阅读http://www.geeksforgeeks.org/maximum-bipartite-matching/和http://en.wikipedia.org/wiki/Ford%E2%80%93Fulkerson_algorithm,我很难理解.似乎这个例子假设每个工作只能接受1个人,每个人想要1个工作.我想知道算法/代码将如何改变,例如,如果v set的容量> 1(可以为该工作雇佣多人)并且u set> 1(每个人想要超过1个工作)？

我正在研究Cormen的"算法简介第2版"中的Ford-Fulkerson算法.在伪代码中描述了有向图G =(V,E)如下,其中f是在VxV上定义的流

FORD-FULKERSON(G, s, t)
    for each edge (u,v) in E(G)
        do f[u, v] = 0
           f[v, u] = 0
    while there is a path p from s to t in the residual network Gf
        do m = min{c(u, v)-f[u, v]: (u, v) is on p}
            for each edge (u, v) on p
                do f[u, v] = f[u, v] + m
                   f[v, u] = - f[u, v]

残差图Gf具有与G相同的顶点,并且具有作为边的那些有序的顶点对(u,v),其中c(u,v)-f(u,v)> 0.(编辑:c是容量函数在开始时给定并在边缘上扩展为零而不是图形的一部分)

我不确定在"双向"存在边缘的情况下该怎么做,例如当边缘及其反转在图中时算法中会发生什么.我假设最小的c(u,v)是图中的原始容量.在(a,b)和(b,a)都是边缘的情况下,我是否需要以某种方式处理残差图中的四条边？在我的设置中,我无法直接处理平行边缘.

我在SO上发现了以下问题: 最大流量 - Ford-Fulkerson:无向图 但我不清楚结果是什么.

假设我在图G =(V,E)上运行Ford-Fulkerson算法,结果是最大流量f _max,它与最小切割Xmin相关联.我有兴趣通过增加图中任何一个边的容量来尽可能地增加流量.我如何识别这个边缘？

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

是否有解决此问题的通用算法？

我试图在 C++ 中实现Edmonds-Karp以获得最大流量，但我的编写方式略有不同：

1. 我没有遍历残差图中的所有边，而是使用邻接表只遍历了原始图中存在的边。
2. 使用最小流量更新残差图时，我没有更新任何后边缘。

有趣的是，当我运行我的代码时，它给了我正确的结果。所以我去了维基百科的例子，它专门展示了如何使用后端。当我将此图输入我的代码时，我又得到了正确答案。我还检查了结果流矩阵，它与维基百科的相同。

有人可以解释为什么我们必须添加和更新 back-edges，并举例说明它们很重要吗？

这是我编写的代码（更新为包括后边缘）：

给定网络G =(V,E),E中的最大流量f和边缘e,我需要找到一个效果算法,以便检测是否存在包含e的一些最小切割.另一个问题是,如果我发现e包含在某些最小切口中,是否可以检测到它是否是切割中最轻的边缘？

我已经考虑过运行Ford-Fulkerson算法,以及增加/减少给定边缘的容量并看看会发生什么,但我还没有提出可能有助于我解决问题的东西.

如果有人能指出我的解决方案,我会很高兴,在此先感谢.

网络中可以有多个最小割.例如:

有4个小时削减,福特 - 富尔克森找到了一个"更接近"s(来源).我们可以对所有网络说同样的话吗？也就是说,Ford-Fulkerson发现最接近源头的切口？如果是的话,我们如何在流动网络中形成"离源最近"的概念？

我想弄清楚在这种情况下我应该如何使用福特富尔克森算法这种情况有点像数独.我们有一个a包含整数值的矩阵.每列的最后一列和每列的最后一行包含整个行/列的总和.

例:

int[][] a = {{1, 3, 5, 9},
             {4, 2, 1, 7},
             {5, 5, 6, *}} // * Is not determined since the sums 
                           // * do not count as summable values.

这就是矩阵中的值并不总是正确的.总和的值并不总是正确的,例如:

int[][] a = {{1, 3, 3, 9},
             {2, 3, 1, 7},
             {5, 5, 6, *}} // * Is not determined since the sums do 
                           // * not count as summable values.

有一个矩阵b,其中包含一个单元格可以满足给定总和的最大差异.例如

int[][] b = {{1, 0, 3},
             {2, 1, 2}}

例如,对于值 …

Ford-Fulkerson算法是否会找到具有n顶点和m边沿O(mn)时间的单位容量流网络（所有边均具有单元容量）的最大流量？

稍微重申一下问题：我们有一个流程图G，它的容量为整数。我们是否可以找到最大流量，其中至少有一条边e（f（e）等于非整数）？

第一次尝试时，我对它有所掩饰，并认为它违反了完整性定理，因此它是错误的，但是在仔细阅读后清楚地表明它没有违反任何规则。显然是真的。

我一直在尝试绘制一个简单的示例以获得可视化效果，但是我似乎什么都没想。谁能告诉我一个流程图示例在哪里工作？

我需要解释什么是节点不相交的路径？以及如何确定有向图中两个节点Source和Sink（t）之间的最大节点不相交路径数。谁能用图形解释。

鉴于无向图G = (V, E)，使得u，v，w在G.一些边

描述一个算法来确定是否

“如果有一条从 u 到 w 的路径通过 v”

下面给出了使用 DFS 的简单算法：

bool checkFunction(){

  graph g; // containing u, w, v
  dfs(v);

  if(isVisited(u) && isVisited(w))
    return true;
  else
    return false;
   
}

对于上述算法，

• 时间复杂度：O(V+E)
• 空间复杂度：O(V)

但是我们可以降低时间复杂度吗？