Как в задаче о максимальном потоке найти все возможные наборы путей, обеспечивающих максимальный поток?

Я понимаю, что Алгоритм Форда-Фулкерсона может найти максимальный поток, который может течь от источника (s) к приемнику (t) в потоковой сети.
Но существует ли алгоритм, который находит все возможные наборы путей, обеспечивающие максимальный поток?

Пример:
В приведенной ниже сети все ребра имеют пропускную способность 1. Несложно заметить, что максимальный поток от s к t равен 3. Но как найти комбинации путей, которые несут этот поток?

Ожидаемые результаты:
Набор путей 1: s-0-1-t, s-2-3-t, s-5-6-t
Набор путей 2: s-0-1-t, s-2-4-t, s-5-6-t
Набор путей 3: s-0-3-t, s-2-4-t, s-5-6-t
Набор путей 4: s-0-4-t, s-2-3-t, s-5-6-t

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

Аналогичный вопрос был задан здесь, но не кажется, получил четкий ответ.


graph algorithm network-flow
person Allen    schedule 18.12.2018    source источник
comment
Можем ли мы предположить, что все дуги являются шапкой 1? Это сильно упрощает задачу.   -  person David Eisenstat    schedule 19.12.2018
comment
@DavidEisenstat Да, все дуги имеют ограничение 1.   -  person Allen    schedule 08.01.2019

Ответы (1)


arrow_upward
0
arrow_downward

В соответствии с вашим комментарием я предполагаю, что все дуги направлены, а емкость равна 1.

Псевдокод высокого уровня

define EnumerateFlows(G, s, t):
    if G has no s-t path:
        yield []  # solution with no paths
    else:
        for P in EnumeratePaths(G, s, t):
            derive G' = G - P
            let s-u be the first arc in P
            derive G'' = G' - {arcs s-v such that v < u}  # ensure canonically ordered solutions only
            for F in EnumerateFlows(G'', s, t):
                yield [P, F...]  # solution with P followed by the elements of F

где возвращаемое значение функции представляет собой список всех yield, созданных в ее теле. Выходные данные нуждаются в постобработке для удаления немаксимальных потоков.

EnumeratePaths несомненно имеет решение для переполнения стека, но для полноты картины,

define EnumeratePaths(G, s, t):
    if s = t:
        yield [s]
    else:
        for u in {successors of s in t}:
            for P in EnumeratePaths(G - {s-u}, u, t):
                yield [s, P...]

Чтобы улучшить EnumerateFlows, стоит добавить проверку, чтобы убедиться, что в остаточном графе все еще существует максимальный поток.

Что касается совета по низкоуровневой реализации, я бы предложил использовать представление списка смежности для G и соединять дуги в списках и вне их. С другой стороны, возможно, ваши графики достаточно малы, чтобы это не имело значения.

person David Eisenstat    schedule 08.01.2019