Что такое расширенный путь?

Говоря о computing network flows, Руководство по разработке алгоритмов говорит:

Традиционные алгоритмы сетевого потока основаны на идее расширений путей и многократно находят путь положительной емкости от s до t и добавляют его к потоку. Можно показать, что поток через сеть является оптимальным тогда и только тогда, когда он не содержит пути увеличения.

Я не понимаю, что такое augmenting paths. Я googled, и нашел:

но все они ссылаются на приведенную выше цитату.

Кто-нибудь может действительно объяснить, что такое augmenting path?

Ответ 1

Путь расширения - это простой путь - путь, который не содержит циклов, - через граф, используя только ребра с положительной мощностью от источника до приемника.

Таким образом, приведенное выше высказывание является каким-то очевидным - если вы не можете найти путь от источника к приемнику, который использует только положительные границы мощности, то поток не может быть увеличен.

Кстати, доказательство этого утверждения не так просто.

Ответ 2

Увеличение означает увеличение - сделать больше. В данной сети потока G=(V,E) и потоке f путь расширения p представляет собой простой путь от source s до sink t в остаточной сети Gf. По определению residual network мы можем увеличить поток на ребре (u,v) пути расширения до емкости Cf(u,v) без нарушения ограничения, в зависимости от того, что (u,v) и (v,u) находится в исходном потоке сеть G. Также максимальное количество, на которое мы можем увеличить поток на каждом ребре в расширенном пути p, называется residual capacity of p. Доказательство можно найти во введении к алгоритмам thomas h. cormen и т.д.

Ответ 3

И как вы узнаете путь увеличения из источника, чтобы потопить? Использование модифицированной версии 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;

Ответ 4

Процесс поиска потоков из источника для итерации. Например, в случае алгоритма Форда-Фулкерсона сначала все потоки на всех ребрах равны нулю. На итерации мы берем значения для каждого пути/ребра, ведущего к тому, чтобы находить потоки, называемые дополнительными путями.