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