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

Question

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

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

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

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

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

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