Я пытаюсь реализовать алгоритм Форда Фулкерсона на Java. Пока у меня есть график с узлами и ребрами. Узлы содержат строку идентификатора и список ребер adjacencyList. Ребра содержат емкость и узел, к которому она ведет.
Я пытаюсь понять псевдокод на странице Википедии и как его реализовать (я использую Java). Это то, что я понимаю до сих пор:
Сначала я установил поток всех ребер в графе равным нулю. (Какой хороший способ представить поток? Непосредственно в ребрах моего графа в качестве переменной?)
Второй шаг — создать остаточный граф, представляющий собой сеть, в которой ребра имеют остаточную пропускную способность: пропускная способность — поток (соответствующих ребер в «нормальном графе»). Затем вы находите путь от источника к приемнику, используя этот остаточный граф, и находите минимальную пропускную способность на этом пути. (Здесь все становится действительно сложно, должен ли я создать совершенно новый граф для остаточного графа или я должен каким-то образом представить его в исходном графе? Как лучше всего?)
Шаг 2 повторяется до тех пор, пока путь не будет найден, но каждый раз, когда он будет найден, вы выполняете шаги 3 и 4:
Для каждого ребра вдоль пути вы добавляете минимальное значение, найденное на шаге 2.
Для каждого ребра в противоположном направлении пути вы вычитаете минимальное значение, найденное на шаге 2.
Шаги 3 и 4 озадачивают меня, так как мне кажется, что прибавлять в одном направлении — это то же самое, что и вычитать в противоположном. Эти сложения и вычитания делаются в графе правильно, а не в остаточном графе?
Был бы очень признателен за помощь, я уже пару часов пытаюсь обдумать это, но я просто не могу этого понять.