理解Dinic的算法有问题吗？

Question

我对Dinic的算法有一个小的不了解，关于它是如何使用残差网络的

所以据我所知的算法如下所示

1-在剩余网络上运行bfs，并根据与源的距离为节点分配级别

2-如果从未到达接收器节点，则终止算法

3运行dfs迭代，严格增加级别，以寻找增加路径，直到达到阻塞流，并求和增加路径的所有瓶颈值，以获得最大流，并根据每个路径的瓶颈更新剩余网络

4-重复1 2 3

现在我的问题是，在dfs迭代期间，这个算法是否使用过残差网络的后向边（从v到u而不是u到v的边来抵消网络的现有流）？

因为我通常是这样表示残边的：-

private static class ResidualEdge implements Comparable<ResidualEdge>{

        public int u, v;
        public long flow;
        public boolean reversed;
        public Edge originEdge;

        public ResidualEdge(int u, int v, long flow, boolean reversed, Edge originEdge) {

            this.u = u;
            this.v = v;
            this.flow = flow;
            this.reversed = reversed;
            this.originEdge = originEdge;
        }

        @Override
        public boolean equals(Object obj) {


            if(obj == null || !(obj instanceof ResidualEdge))
                return false;

            ResidualEdge  edge = (ResidualEdge)obj;

            return edge.u == u && edge.v == v && edge.flow == flow && this.originEdge == edge.originEdge && this.reversed == edge.reversed;
        }

        @Override
        public int hashCode() {


            return Integer.hashCode((int) (flow + u + v + Boolean.hashCode(reversed)));
        }


        @Override
        public int compareTo(ResidualEdge o) {

            if(flow > o.flow)
                return 1;

            else if (flow < o.flow)
                return -1;

            return 0;
        }
    }

原始边是对原始网络的原始边的引用，剩余边表示要取消的剩余容量或流量，以便更容易地更新原始网络

现在我问这个问题，因为如果Dinic的算法不使用反向边，那么我可以忽略表示反向边，算法会简单得多

Answer 1

是的，它使用反向边缘。

示例：

假设B->C边在B->D边之前被处理，在没有反向边的情况下，该算法将计算出最大流只有3，而实际上是4。

通常在竞争规划中,使用Dinic算法时,图不是以边的形式存储,而是以矩阵的形式存储NxN,首先存储边i->j的剩余容量,然后存储流过边i->j的流。这些矩阵占用了O(n*n)内存，但Dinic的算法无论如何都是以O(n*n*m)运行的，所以当Dinic的算法运行得足够快时，节点的数量就足够小，这样就可以存储矩阵了。