java - 理解 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 算法无论如何都以 O(N*N*M) 运行，因此当 Dinic 算法运行得足够快时，那么节点数量就足够小，因此您可以存储矩阵。