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

Зависит от алгоритма поиска увеличивающего пути. Требует O(max f ) таких поисков. Найти любой увеличивающий путь. Увеличить поток по всем его рёбрам на минимальную из их остаточных пропускных способностей. Повторять, пока увеличивающий путь есть. Алгоритм работает только для целых пропускных способностей. Усовершенствование алгоритма Эдмондса-Карпа (но хронологически был найден раньше). Вместо потока оперирует с предпотоком. Отличие в том, что для любой вершины u, кроме источника и стока, сумма входящих в неё потоков для потока должна быть строго нулевой (условие сохранения потока), а для предпотока — неотрицательной.

Увеличение потока (или Алгоритм Форда-Фалкерсона)

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

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

Алгоритм поиска в ширину (breadth first search), BFS.

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

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

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

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

Это значит, что нам задан ненаправленный граф и по ребру можно пройти в любом направлении (туда-обратно). Т.е. допустим в ячейке массива dist будем хранить расстояние до вершины от «завода». Аналогично массивами будем пользоваться, при обходе графа для того, чтобы отмечать уже посещенные вершины (mark), записывать сколько ящиков привезли (push), и откуда мы в вершину приехали (pred). ОК. Отлично. Знаем, как преобразовать нашу карту в граф. А как мы будем доставлять ящики до аэропорта?

BFS является одним из самых основных алгоритмов, составляющих основу многих других. Простое описание (рисунок будет ниже). Мы сейчас стоим в некоторой стартовой (завод) вершине , из которой по ребрам видны только соседние вершины. При этом те вершины, в которых однажды побывали — игнорируем (ни шагу назад).

Вот, в общем, и вся логика алгоритма. Т.е. в вершину мы попали из вершины pred. Алгоритмы буду, если можно так выразиться, рассказывать, т.к. в сети предостаточно их описаний. Т.е. по дороге из в мы везем F ящиков. Эта сумма называется избыточным потоком в вершину, а вершина с положительным избыточным потоком называется переполненной.