Я использую bfs, чтобы найти добавочный путь. Но он производит одинаковый путь каждый раз. Но для алгоритма ford fulkerson требуется, чтобы каждый раз выбирался каждый путь от источника к потоку , так может кто-нибудь предложить мне, как изменить bfs так, чтобы он создавал различный путь каждый раз между источником и sink.graph направлен и взвешенмодификация bfs для алгоритма ford fulkerson, чтобы найти путь расширения
Вам нужно убедиться, что BFS игнорирует края, где использовалась вся емкость , Обычно BFS запускается на так называемой остаточной сети, в которой каждый объем ребер указывает, сколько емкости остается на этом краю (учитывая поток, который вы отправили через этот край). Вы можете либо сохранить отдельный остаточный график, либо вы можете иметь неявный, заставив BFS посмотреть разницу между исходной емкостью и текущим потоком для каждого ребра (и обработать край как отсутствующий, если его емкость равна нулю).
, но bfs выбирает путь, основанный на no.vertices, я имею в виду, что самый короткий путь основан на нет. вершин от источника до потолка – shalini
Я меняю емкость, но это не помогает – shalini
Да, при первом запуске BFS выберет самый короткий путь. Однако после того, как этот путь будет найден, Ford-Fulkerson отправит как можно больше потока по этому пути; это будет использовать всю пропускную способность по крайней мере на одном из краев, таким образом, «нарушая» путь. Следующий BFS обязательно найдет другой путь, потому что по крайней мере один из краев старого пути теперь непригоден. Как я уже сказал, вам нужно убедиться, что края, где используется вся емкость, будут игнорироваться BFS. –
Каждый раз используйте случайного ребенка. – Mark