проблема с пониманием алгоритма dini c?

Question

У меня есть небольшая ошибка в понимании алгоритма Дини c о том, как он использует остаточную сеть

, поэтому, насколько я понимаю, алгоритм следующий

1 - запустить bfs в остаточной сети и назначить уровни узлам на основе расстояния от источника

2 - если узел приемника не был достигнут, завершить алгоритм

3 - запустить итерации dfs, идущие со строго увеличивающимися уровнями для поиска путей дополнения до достижения блокирующего потока и суммирования по всем значениям узких мест путей дополнения для получения максимального потока и обновления остаточной сети в соответствии с узким местом каждого пути

4 - повторите 1 2 3

Теперь мой вопрос заключается в том, использует ли этот алгоритм когда-либо обратные края остаточной сети (те, которые идут от v к u вместо u к v для отмены существующего потока сети) во время итерации dfs?

, потому что я обычно представляю остаточные ребра следующим образом: -

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 являясь ссылкой на исходный край исходной сети, остаточный край представляет его оставшуюся пропускную способность или поток для отмены, чтобы упростить обновление исходной сети

, теперь я спрашиваю об этом, потому что если dini c ' В алгоритме не используются перевернутые ребра, тогда я могу просто игнорировать представление перевернутых ребер, и алгоритм будет намного проще

Answer 1

Да, используются перевернутые ребра.

Пример:

При условии, что ребро B -> C будет обработанный до края B-> D, без перевернутых ребер этот алгоритм вычислит, что максимальный поток равен только 3, но на самом деле он равен 4.

Обычно в конкурентном программировании при использовании алгоритма Дини c это значительно граф легче хранить не как ребра, а как матрицы NxN - первый хранит остаточную емкость ребра i-> j, второй хранит поток через ребро i-> j. Эти матрицы занимают O (N * N) памяти, но алгоритм Дини c в любом случае работает в O (N * N * M), поэтому, когда алгоритм Дини c может работать достаточно быстро, тогда число узлов достаточно мал, чтобы вы могли хранить матрицы.