проблема с пониманием алгоритма Диника?

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

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

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

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


java algorithm network-flow
person Xenouth    schedule 18.01.2020    source источник

Ответы (1)


arrow_upward
0
arrow_downward

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

Пример:

введите здесь описание изображения

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

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

person ardenit    schedule 18.01.2020
comment
да, я понимаю, но как мне сохранить обратные остаточные края и иметь возможность различать их и между передними краями? и как мне обновить их соответственно? - person Xenouth; 19.01.2020
comment
Вам не нужно делить ребра на передние и обратные. Остаточная сеть содержит два ребра для каждого ребра, и эти два ребра одинаковы для алгоритма. - person ardenit; 19.01.2020
comment
Пусть c[i][j] будет остаточной емкостью ребра i -> j (по умолчанию 0). Пока вы строите граф, если вы хотите добавить ребро v -> u с пропускной способностью c0, то вы просто увеличиваете c[v][u] на c0. Во время алгоритма, если вы хотите увеличить поток ребра v -> u на f0, вы уменьшаете c[v][u] на f0 и увеличиваете c[u][v] на f0. Пока вы делаете BFS, чтобы найти уровни каждого узла, условие наличия ребра v -> u в остаточной сети равно c[v][u] != 0. - person ardenit; 19.01.2020
comment
Пожалуйста, прочитайте cp-algorithms.com/graph/dinic.html, эта реализация даже хранит ребра в виде списков. - person ardenit; 19.01.2020