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

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

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

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

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

Ответы на вопрос(1)

Ваш ответ на вопрос