algorithm - 福特富尔克森算法的bfs修改，寻找增广路径

Question

我正在使用 bfs 来查找增广路径。但它每次都产生相同的路径。但是福特富尔克森算法要求，我们每次从源到接收器都选择不同的路径，所以有人可以建议我如何修改 bfs 以使其产生不同的路径source 和 sink.graph 之间的每次路径都是有向和加权的

Answer 1

您需要确保 BFS 忽略已使用所有容量的边缘。通常，BFS 在所谓的残差网络上运行，其中每个边缘容量都表明该边缘上剩余多少容量（给定您通过该边缘发送的流量）。您可以维护一个单独的残差图，也可以通过让 BFS 查看每条边的原始容量和当前流量之间的差异来创建一个隐式残差图（如果边的容量为零，则将其视为不存在）。