Теперь  принимаем во внимание: смежность (соседство) вершин графа, направленные пропускные способности ребер, но пока не рассматриваем  расстояния.

      Когда мы увеличиваем поток (ящиков) от вершины [u] к вершине [v], мы естественно выполняем операцию: F[u][v] += flow, но в обратную сторону мы уменьшаем поток F[v][u] -= flow; Вот почему. Возможна такая ситуация:

На рисунке: на ребрах – подписан (поток / пропускная способность)

В первый раз, пронеся поток в 3 ящика  в вершину [i] и обнаружив ребро [i]-[j]: Мы перевезли min(push[i], C[i][j] – F[i][j]) = min(3, 3-0) = 3 ящика, и отметили это как F[i][j] += 3, а в обратную сторону мы поставили: F[j][i] -= 3.

      Во  второй раз, оказавшись в вершине [j], мы пытаемся протолкнуть min(push[j], C[j][i]-F[j][i]) = min(6, 0-(-3)) = min(6, 3) = 3 в вершину [i]. Против потока +3, мы толкнули -3 ящиков и получили компенсацию потока по этой дороге. Зато в направлении к «аэропорту» в следующей итерации мы дополнительно отправили остальные 3 ящика.

      Интерпретация: из склада [j] мы позвонили в склад [i], и сказали: «Оставьте себе свои 3 ящика – найдите им другое применение, мы вместо них привезли своих 3». Хоть алгоритм сам любезно нашел им применение.

Продолжаем искать поток:

      Мы  договорились, настойчиво продолжать искать пути к «аэропорту», пока удается, и провозить по ним ящики. Грубо  говоря, это и называется алгоритмом поиска максимального потока, или  алгоритм Форда-Фалкерсона. А так  как мы для «открытия» новых маршрутов  доставки применяем BFS – это называется алгоритмом Эдмондса-Карпа.

      Когда до упора «насытим» дороги транспортировкой своих ящиков, мы ответим Партнеру на вопрос «Сколько ящиков в день мы сможем провозить в аэропорт?». Но пора подумать и о собственных  амортизационных расходах… Шины, бензин, износ…

      Уже стало ясно, что при поиске BFS’ом по графу нам придется сталкиваться с отрицательными величинами, такими как обратный поток (а он имеет следствия в «финансовом выражении»), даже если речь идет о расстояниях. В общем, пора уже учитывать дополнительно и расстояния…

      Расстояния. Пора целиком добить эту задачу: смежность (соседство) вершин графа, направленные пропускные способности ребер, расстояния.

Продолжаем запускать  BFS, пока не загрузим дороги нашими ящиками «до упора»:

Теперь посмотрим на то, что получилось. Будем проверять со стороны «аэропорта»: если какой-то ящик к нам добрался за расстояние 15 км., значит если бы мы от него отказались – то, сэкономили бы 15 км. проезда (т.е. вычитаем 15), но нужно  по возможности попробовать найти (пристроить) ему другой путь движения.

      Попробуем пройтись по ребрам в прямом (по свободным  дорогам) и обратном (толкая назад  и экономя) направлениях от «аэропорта»:

      На  рисунке: на ребрах – подписан (поток / пропускная способность), а сверху — расстояние

На картинке сверху – мы обнаружили «отрицательный цикл» -6, все так же шагая по доступным (свободным или толкая против потока) ребрам. Делая в нем один оборот, мы можем сократить расстояние для  участвующих в нем вершин на -6. А это значит, что можно сэкономить на доставке транспортируемых в цикле  ящиков. Просто пустив ящики «по  циклу». На картинке сверху – мы сэкономим 6 км. пути.

      Теперь  мы знаем, как решить поставленную задачу, но для того, чтобы обнаруживать эти циклы… Рассмотрим:

2.4 Алгоритм Беллмана-Форда 

Он применяется  для нахождения кратчайшего расстояния от вершины [s] до остальных вершин. Но в отличие от BFS, коротким путь будет не в смысле количества ребер графа на этом пути, а в смысле суммированного «расстояния» по ребрам пути.

      Но  он нам понадобится не для этого. Одна из его ключевых особенностей, отличающая его от алгоритма Дейкстры, заключается в том, что он способен работать на графах, где вес ребер  может быть задан отрицательным  числом. Алгоритм может обнаруживать побочное явление таких графов —  циклы отрицательной величины. Что  нам и надо!

Алгоритм несколько  сложней. Данная реализация несколько  не коррелирует с библией Кормена, но тоже отлично работает. По виду она  несколько напоминает BFS, потому и постараюсь объяснить, отталкиваясь от него.

      Начиная с некоторой вершины, просматриваем  по «доступным» ребрам соседние вершины, и пытаемся улучшить до них расстояние в массиве dist[..] и сделать как можно меньше. Этот процесс называется «релаксация». Если «нащупали» (по ребрам) такие вершины, то обновляем им расстояния и заносим их вершины в очередь «попробовать из них улучшить граф». Очень похоже на BFS! Но мы не отмечаем вершины («уже побывали») и если придется зайти в одну вершину дважды, то сделаем это.

      Но  вот вопрос, готовы ли мы к тому, что  будут попадаться «отрицательные циклы», по которым можно вечно крутиться, уменьшая расстояние до вершин? Процесс  не закончится. Поэтому, «радиус осмотра» вершин ограничим числом N (числом самих вершин). Этого будет гарантированно достаточно для того, чтобы просчитать минимальное расстояние до любой вершины, а главное алгоритм в любом случае завершится.

Для этого поместим первую вершину в очередь, и после  нее «заглушку», таким образом  обозначив, что в очереди находятся  вершины в «радиусе осмотра 0». Когда, вынимая из очереди следующую  вершину, вдруг достанем нашу «заглушку» — поставим новую, обозначив следующий  «радиус осмотра». Вот, в общем, и  вся логика алгоритма. =)

Улучшение расстояние до вершин проверяется следующим  неравенством:

dist[v] > dist[u] + edge_cost(u, v)

На рисунке: на ребрах – длина, а в подсказке –  найденное в текущий момент кратчайшее расстояние Отметим основные особенности (в отличие от BFS):

в вершину мы можем  попасть несколько раз, если расстояние до нее было улучшено. Зайдя потом  в эту вершину, мы попробуем улучшать расстояния уже из нее

в очередь помещаются вершины, до которых было улучшено расстояние

от своего завода мы радиально (волнообразно) по расстояниям (а не по ребрам) находим остальные  вершины

смотреть будем  только по свободным дорогам, по которым  можно перевезти (либо толкнуть обратно) ящики. Следовательно, учитывая расстояния и пропускную способность

      Просмотр  графа в «радиусе N (количества вершин)»  гарантирует, что для всех вершин мы нашли минимальное расстояние. И больше нечего уменьшать. А если какие-то из вершин «втянуты» в «отрицательный цикл», то его легко можно будет  обнаружить, проверив на нарушение  равенства. Ведь в цикле расстояния бесконечно уменьшаются:

dist[v] > dist[u] + edge_cost(u, v) 

Поэтому, если для  вершины [v] это неравенство выполнится, значит – она участвует в отрицательном  цикле. Что и нужно! «Разматывая» от нее путь, по которому мы в нее  попали, мы будем крутиться по (её) циклу.

Все – цикл обнаружен! Осталось всего-то поток ящиков по нему направить «вспять», и тем самым  увеличить эффективность ведения  бизьнеса.

Алгоритм Максимального  потока минимальной стоимости:

Запускаем нахождение Максимального потока Эдмондса-Карпа:

Пока BFS находит путь от «завода» до «аэропорта»

провозим по нему ящики

Пока алгоритм Беллмана-Форда  находит «отрицательные циклы»:

Поворачиваем поток  в «отрицательных циклах» вспять.

Получили максимальный поток минимальной стоимости (расстояния)

 

 

Список  использованной литературы

1. Емеличев  В.А. Лекции по теории графов. -М.: Наука, 1990, -384 с.
2. Горбатов В. А. Основы дискретной математики. - М.: Высшая школа, 1986.- 311 с.
3. Кристофидес Н. Теория графов. Алгоритмический подход. -М.: Мир, 1978, -432 с.
4. Нефедов В.Н., Осипова В.А. Курс дискретной математики: Учеб. пособие. –М.: Изд-во МАИ, 1992. -398 с.
5. Окулов С.М. Программирование в алгоритмах. –М.: Бином, 2004. -341 с.

 

Приложение. Текст программы

int C[MAX_N][MAX_N];   

int F[MAX_N][MAX_N];   

int P[MAX_N][MAX_N];   

int push[MAX_N];       

int mark[MAX_N];       

int pred[MAX_N];       

int dist[MAX_N];       

int N, M, s ,t;        

int max_flow;

int min_cost;

void file_read()

{

    int u, v, c, p;

    in >> N >> M >> s >> t; N++;

        for(int i = 0; i < M; i++)

    {

        in >> u >> v >> c >> p;

        C[u][v] = c;

        P[u][v] = p;

        P[v][u] = -p;

    }

}

int edge_cost(int u, int v)

{

    if( C[u][v] - F[u][v] > 0 ) return P[u][v];

    else return MAX_VAL;

}

int check_cycles()

{

    for(int u = 1; u < N; u++)

        for(int v = 1; v < N; v++)

            if( dist[v] > dist[u] + edge_cost(u, v) )

                return u;

    return MAX_VAL;

}

void init()

{

    for(int i = 1; i < N; i++)

    {

        mark[i] = 0;

        push[i] = 0;

        pred[i] = 0;

        dist[i] = MAX_VAL;

    }

} 

int bf(int s)

{

    init();

    queue<int> Q;

    pred[s] = s;

    dist[s] = 0;

    Q.push(s);

    Q.push(MAX_N);

        int u, series = 0;

    while( !Q.empty() )

    {

        while( Q.front() == MAX_N )

        {

            Q.pop();

            if( ++series > N ) return check_cycles();

            else Q.push(MAX_N);

        } 

        u = Q.front(); Q.pop();

        for(int v = 1; v < N; v++)

            if( dist[v] > dist[u] + edge_cost(u, v) )

            {

                dist[v] = dist[u] + edge_cost(u, v);

                pred[v] = u;

                Q.push(v);

            }

    }

} 

int bfs(int s, int t)

{

    init();

    queue<int> Q;

    mark[s] = 1;

    pred[s] = s;

    push[s] = MAX_VAL;

      Q.push(s);

    while( !mark[t] && !Q.empty() )

    {

        int u = Q.front(); Q.pop();

        for(int v = 1; v < N; v++)

            if( !mark[v] && (C[u][v]-F[u][v] > 0) )

            {

                push[v] = min(push[u], C[u][v]-F[u][v]);

                mark[v] = 1;

                pred[v] = u;

                Q.push(v);

            }

    }

    return mark[t];

}

void max_flow_ff()

{

    int u, v, flow = 0; 

    while( bfs(s, t) )

    {

        int add = push[t];

        v = t; u = pred[v];

        while( v != s )

        {

            F[u][v] += add;

            F[v][u] -= add;

            v = u; u = pred[v];

        }

        flow += add;

    }

    max_flow = flow;

} 

void min_cost_flow()   

{

    max_flow_ff();

        int u, v, flow = 0;

    int add = MAX_VAL;

    int neg_cycle;

    neg_cycle = bf(t);