49

在谈到 时computing network flows，算法设计手册说：

传统的网络流算法基于增广路径的思想，反复寻找从 s 到 t 的正容量路径并将其添加到流中。可以证明，当且仅当它不包含增广路径时，通过网络的流是最优的。

我不明白是什么augmenting paths。我用谷歌搜索，发现：

但他们都引用了上面的报价。

谁能真正清楚地解释什么是 a augmenting path？

4

4 回答 4

53

增广路径是一条简单的路径 - 一条不包含循环的路径 - 仅使用从源到汇的具有正容量的边通过图。

所以上面的陈述在某种程度上是显而易见的——如果你找不到从源到汇的只使用正容量边的路径，那么流量就不能增加。

顺便说一句，该陈述的证明并不那么容易。

于 2012-05-01T11:41:23.710 回答
7

增加意味着增加——使更大。在给定的流网络G=(V,E)和流f中，增广路径是残差网络中从到到p的简单路径。根据 的定义，我们可以在不违反约束的情况下将增广路径边缘的流量增加一个容量，无论和是在原始流量网络中的哪一个。此外，我们可以在增广路径 p 中增加每条边上的流量的最大量称为。证明可以在 thomas h 的算法导论中找到。科门等...source ssink tGfresidual network(u,v)Cf(u,v)(u,v)(v,u)Gresidual capacity of p

于 2013-04-18T10:57:44.987 回答
4

你如何找出从源到汇的增广路径？使用 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;
于 2013-12-29T03:12:42.703 回答
0

迭代地查找从源到汇的流的过程。例如，在 Ford-Fulkerson 算法的情况下，最初所有边上的所有流都为零。在迭代中，我们获取每条路径/边的值，引导我们找到称为增广路径的流。

于 2015-12-10T04:48:22.293 回答