Алгоритм Эдмондса-Карпа для графа, который имеет узлы с пропускной способностью

Question

Я реализую этот алгоритм для ориентированного графа.Но интересная вещь об этом узле графа также имеет свои собственные пропускные способности.Я думаю, что это тонкое изменение первоначальной проблемы должно быть обработано особым образом.Потому что в исходной задаче максимального потока было нормально найти любой путь от начала до конца (фактически, в алгоритме Эдмондса-Карпа нам нужно сделать BFS и выбрать первый путь, который достигает конечного узла) Но с этим узломРасширение емкости, мы должны быть более осторожны с заданием «выбор пути».Я знаю это, потому что я реализовал оригинальный алгоритм и обнаружил, что получаю меньшие значения потока, чем максимальный поток, я сомневаюсь, что это связано с этими ограничениями пропускной способности узла.

Я приложил много усилий для этогои выдвинул некоторые идеи, такие как преобразование исходного графа в граф, который не имеет ограничений по емкости для узлов, путем добавления циклов self (добавление циклов self к каждому узлу и поиск путей, включающих эти циклы self для каждого узла в пути) или добавлениевиртуальные узлы и ребра, вес которых превосходит начальные ограничения емкости узла). Однако я не уверен, что любое из них является хорошим решением для этой проблемы.

Любая идея будет высоко оценена.

Заранее спасибо.

Answer 1

Простое сокращение от задачи максимального потока с пропускной способностью узла до обычной задачи максимального потока:

Для каждой вершины v в вашем графе замените двумя вершинами v_in и v_out.Каждый входящий фронт в v должен указывать на v_in, а каждый исходящий фронт в v должен указывать в v_out.Затем создайте одно дополнительное ребро от v_in до v_out с емкостью c_v, емкостью вершины v.

Так вы просто запустите Edmunds-Karp на преобразованном графе.

Итак, допустим, у вас есть следующий граф в вашей задаче (вершина v имеет емкость 2):

s --> v --> t
   1  2  1

Это будет соответствовать этому графику в задаче с максимальным потоком:

s --> v_in --> v_out --> t
   1        2         1

Должно быть очевидно, что полученный максимальный поток является решением (и это не особенно сложно доказать).