algorithm - 为 ford fulkerson 算法修改 bfs，以找到增广路径

Question

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

Answer 1

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