また、ソースからシンクへの拡張パスをどのように見つけますか? BFS の修正版を使用します。シンクに到達するまでソースから BFS を実行し、残りの容量がある場合にのみエッジをトラバースします (つまり、そのエッジの最大容量 - 電流フロー > 0)。ソースからシンクへのこのパスでは、そのパスを通過できる最大フローである最小残存容量を維持します。アイデアを得るための高レベルのコード スニペット:
bool maxFlowAchieved = false;
int maxFlow = 0; // keeps track of what is the max flow in the network
while(!maxFlowAchieved)
{
//BFS returns collection of Edges in the traversal order from source to sink
std::vector<Edge*> path = BFS(source, sink);
maxFlowAchieved = path.size() == 0; // all paths exhausted
if(maxFlowAchieved)
break;
// traverse each edge in the path and find minimum residual capacity
// edge->residual = edge->maxCapacity - edge->currentflow
int allowedFlow = GetMinResidualOnPath(path);
// Now add additional flow to each edge in the path.
// i.e. for each edge in path, edge->currentflow += allowedFlow
// clearly, edge->currentflow + allowedFlow <= edge->maxCapacity
SaturatePath(path, allowedFlow);
maxFlow += allowedFlow;
}
return maxFlow;