я использую bfs, чтобы найти увеличивающийся путь. но он каждый раз создает один и тот же путь. но алгоритм форда фулкерсона требует, чтобы мы каждый раз выбирали разные пути от источника к приемнику, поэтому может ли кто-нибудь предложить мне, как изменить bfs, чтобы он производил разные путь каждый раз между источником и стоком.граф направляется и взвешивается
модификация bfs для алгоритма форда фулкерсона, чтобы найти увеличивающийся путь
comment
Каждый раз используйте случайный ребенок.
- person Mark   schedule 04.07.2012
Ответы (1)
Вы должны убедиться, что BFS игнорирует ребра, где была использована вся емкость. Обычно BFS запускается в так называемой остаточной сети, в которой емкость каждого края указывает, сколько емкости осталось на этом крае (с учетом потока, который вы отправили). через этот край). Вы можете либо поддерживать отдельный остаточный граф, либо иметь неявный, заставив BFS смотреть на разницу между исходной пропускной способностью и текущим потоком для каждого ребра (и рассматривать ребро как отсутствующее, если его пропускная способность равна нулю).
person
Aasmund Eldhuset
schedule
04.07.2012
но bfs выбирает путь на основе no.vertices, я имею в виду, что кратчайший путь основан на no. вершин от истока до стока
- person shalini; 04.07.2012
я меняю емкость, но это не помогает
- person shalini; 04.07.2012
Да, поэтому при первом запуске BFS выберет кратчайший путь. Однако после того, как этот путь будет найден, Форд-Фалкерсон направит по этому пути как можно больше потока; это будет использовать всю емкость по крайней мере на одном из ребер, тем самым разрывая путь. Следующая BFS обязательно найдет другой путь, потому что по крайней мере одно из ребер на старом пути теперь непригодно для использования. Как я уже сказал, вы должны убедиться, что границы, на которых используется вся емкость, будут игнорироваться BFS.
- person Aasmund Eldhuset; 04.07.2012
Может ли кто-нибудь помочь мне, как использовать алгоритм Форда Фулкерсона для практических приложений, таких как выбор проекта, планирование авиакомпаний
- person shalini; 05.07.2012