модификация bfs для алгоритма форда фулкерсона, чтобы найти увеличивающийся путь

я использую bfs, чтобы найти увеличивающийся путь. но он каждый раз создает один и тот же путь. но алгоритм форда фулкерсона требует, чтобы мы каждый раз выбирали разные пути от источника к приемнику, поэтому может ли кто-нибудь предложить мне, как изменить bfs, чтобы он производил разные путь каждый раз между источником и стоком.граф направляется и взвешивается


graph algorithm data-structures breadth-first-search ford-fulkerson
person shalini    schedule 04.07.2012    source источник
comment
Каждый раз используйте случайный ребенок.   -  person Mark    schedule 04.07.2012

Ответы (1)


arrow_upward
2
arrow_downward

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

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