理解 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;
        }
    }

originEdge是对原始网络的原始边缘的引用，剩余边缘表示它的剩余容量或流量取消以使其更容易更新原始网络

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

Answer 1

是的，它使用反边。

示例：

假设B->C边先于B->D边处理，没有反向边这个算法会计算出最大流只有3，但实际上是4。

通常在竞争性编程中，当使用 Dinic 算法时，将图形存储为 NxN 矩阵而不是边要容易得多 - 首先存储边 i->j 的剩余容量，其次存储流经边 i->j 的流量。这些矩阵占用 O(N*N) 内存，但 Dinic 的算法无论如何运行s 在 O(N*N*M) 中，所以当 Dinic 的算法可以运行足够快时，节点的数量是小到可以存储矩阵。

理解 dinic 的算法有问题吗？

issue with understanding dinic's algorithm?

java

algorithm

network-flow