javaalgorithmnetwork-flow

issue with understanding dinic's algorithm?


I have a have a small miss understanding of dinic's algorithm about how it use the residual network

so the algorithm as far as i understand is the following

1- run bfs on the residual network and assign levels to the nodes based on the distance from the source

2- if the sink node was never reached terminate the algorithm

3- run dfs iterations going with strictly increasing levels to find augment paths until a blocking flow is reached and sum over all bottleneck values of the of the augment paths to get the maximum flow and update the residual network according to the bottlneck of each path

4- repeat 1 2 3

now my question is does this algorithm ever uses the backward edges of the residual network (the ones that goes from v to u instead of u to v to cancel existing flow of the network) during dfs iterations?

because i usually represent residual edges this way:-

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

the originEdge being a reference to the original edge of the original network that the residual edge represent it's remaining capacity or flow to cancel to make it easier to update the original network

now I am asking this because if dinic's algorithm doesn't use reversed edges then I can just ignore representing reversed edges and the algorithm would be much simpler


Solution

  • Yes, it uses reversed edges.

    Example:

    enter image description here

    Assuming that B->C edge will be processed before B->D edge, without reversed edges this algorithm will calculate that max flow is only 3, but in fact it is 4.

    Usually in competitive programming when using Dinic's algorithm it's much easier to store graph not as edges, but as matrices NxN - first stores residual capacity of edge i->j, second stores flow through edge i->j. These matrices take O(N*N) memory, but Dinic's algorithm anyway runs in O(N*N*M), so when Dinic's algorithm can run fast enough, then the number of nodes is small enough so you can store matrices.