Задание 3. Построить увеличивающие пути для меток, найденных в задании 2 ■
Пусть дуга (xi, xj) входит в некоторый путь p (не обязательно от источника к стоку). Дуга (xi, xj) называется прямой дугой пути p, если вершина xi расположена на пути p ближе к его на-чалу, чем вершина xj, и называется обратной дугой пути p, в противном случае. Заметим, что одна и та же дуга может быть прямой в одном пути и обратной в другом. Путь p от источника к стоку, во всех прямых дугах которого поток uj < cj, а во всех обратных дугах поток uj > 0, называется увеличивающим путём.
Утверждение 4. Путь p от источника к стоку, построенный алгоритмом 2 по меткам, пост-роенным алгоритмом 1, является увеличивающим путём ■
3. Алгоритм вычисления инкремента увеличивающего пути. Пусть путь p = z 1→ z 2→...→ zk является увеличивающим путём.
1. Положим D = 
, i = 0.
2. i = i + 1.
3. Положим
Di = 
4. Положим D = min{ D, Di }.
5. Если i < k -1, возвращаемся к шагу 2; в противном случае алгоритм 3 прекращает работу ■
Найденное значение D является той «добавкой», на которую могут быть увеличены потоки во всех дугах пути p (именно поэтому он назван «увеличивающим»).
Пример 9. Вычислим инкремент увеличивающего пути p = x 1→ x 3 → x 5→ x 6, найденного в примере 8 (см. последнюю строку таблицы 2.5). Положим D = = 12.
Далее:
i = 1, vj = (x 1, x 3), cj = 2, uj = 0, D 1 = cj - uj = 2, D = min(D, D 1) = 2;
i = 2, vj = (x 3, x 5), cj = 1, uj = 0, D 2 = cj - uj = 1, D = min(D, D 2) = 1;
i = 3, vj = (x 5, x 6), cj = 4, uj = 0, D 3 = cj - uj = 4, D = min(D, D 3) = 1.
Таким образом, инкремент увеличивающего пути p = x 1→ x 3→ x 5→ x 6 равен 1. Это значит, что потоки во всех дугах данного пути могут быть увеличены на 1 ■
Задание 4. Найти инкременты увеличивающих путей, найденных в задании 3 ■
4. Алгоритм построения нового потока u'. Новый поток u' определяется по заданному потоку u, построенному увеличивающему пути p и вычисленному инкременту D этого пути следующей формулой:
= 
(j = 1, 2,..., m). (9)
Пример 10. Найдём новый поток u' для сети, рассмотренной в примерах 7 - 9. Все три дуги в пути p = x 1→ x 3→ x 5→ x 6 являются прямыми. «Старые» потоки по этим дугам были равны 0, а новые равны 1. Учитывая нумерацию дуг в данной сети (см. рис.2), получаем u' = (2, 1, 1, 1, 1, 1, 0, 2, 1).
Задание 5. Найти новые потоки по потокам из задания 1 и инкрементам, найденным в за-дании 4 ■
Утверждение 5.
1. Вектор u' с компонентами, определенными формулой (9), является потоком в сети S;
2. Р (u') = Р (u) + D, (10)
где через Р (u) обозначена величина потока u (см. конец раздела 1 перед примером 2) ■
Таким образом, по любому потоку u, не являющемуся максимальным, можно построить поток u' с бóльшей величиной Р (u'). Именно это построение (состоящее из рассмотренных вы-ше четырёх этапов) и лежит в основе АФФ.
Для завершения описания алгоритма нам понадобится почти очевидное
Утверждение 6. Нулевой вектор u = (0, 0,..., 0) является потоком в сети ■
Алгоритм Форда-Фалкерсона (АФФ)
1. Положить u = (0, 0,..., 0).
2. Выполнить алгоритм расстановки меток по потоку u. При выходе из этого алгоритма на шаге 7 АФФ завершает работу; поток u является максимальным. При выходе из этого алгоритма на шаге 3 перейти на следующий шаг 3 АФФ.
3. Построить увеличивающий путь p между источником и стоком, исходя из найденных меток.
4. Вычислить инкремент D найденного увеличивающего пути, исходя из потока u.
5. Построить новый поток u' по формуле (9), исходя из потока u, пути p и декремента D.
6. Положить u = u' и вернуться на шаг 2 ■
Утверждение 7. При целочисленных пропускных способностях сj (j = 1, 2,..., m) все пото-ки, построенные АФФ, будут целочисленными, и процесс построения потоков оборвётся за ко-нечное число шагов ■
Это достаточно простое утверждение не означает, что при нецелочисленных пропускных способностях АФФ обязательно будет «циклиться». Более того, при разумном (а не произволь-ном) выборе вершины из множества помеченных и не просмотренных вершин на шаге 1 алго-ритма расстановки меток можно не только гарантировать конечность АФФ при любых пропус-кных способностях, но и дать полиномиальную оценку числа необходимых операций.
Пример 11. Используя АФФ, найти максимальный поток в сети, показанной на рис.10.
\ 
Рис.10
В соответствии с АФФ начнём с нулевого потока.
1. Положим u = (0, 0, 0, 0, 0).
2. Найдём метки, как это делалось в примере 7. Определим исходную таблицу, являющу-юся инициализацией для расстановки меток:
Таблица 3. Инициализация основной таблицы
и просто выпишем результаты последовательных итераций:
Таблица 3.1. Итерация 1
Таблица 3.2. Итерация 2
Поскольку сток (вершина 4) помечен, метки построены. Они приведены в последней строке таблицы 3.2.
3. Построим увеличивающий путь (см. алгоритм 2). Он таков: 1→2→4.
4. Найдём инкремент (см. алгоритм 3). Положим D = 8; тогда D 1 = 8, D 2 = 6.
5. Найдём новый поток (см. алгоритм 4). Положим u' = (6, 0, 0, 6, 0) и перейдём на шаг 2.
2. Найдём метки, как это делалось в примере 7. Определим исходную таблицу, являющу-юся инициализацией для расстановки меток:
Таблица 4. Инициализация основной таблицы
и просто выпишем результаты последовательных итераций:
Таблица 4.1. Итерация 1
Таблица 4.2. Итерация 2
Заметим, что исходя из вершины 2, мы не пометили новые вершины. Вершину 4 нельзя поме-тить, поскольку поток в дуге (2, 4) равен ограничению, а вершину 3 нельзя пометить, потому что она уже была помечена. Единственное изменение на 2-ой итерации состоит в том, что вершина 2 перешла в состояние 3 из состояния 2.
Таблица 4.3. Итерация 3
Поскольку сток оказался помеченным, то метки построены. Они приведены в последней строке таблицы 4.3.
3. Построим увеличивающий путь (см. алгоритм 2). Он таков: 1→3→4.
4. Найдём инкремент (см. алгоритм 3). Положим D = 5; тогда D 1 = 5, D 2 = 4.
5. Найдём новый поток (см. алгоритм 4). Положим u' = (6, 4, 0, 6, 4) и перейдём на шаг 2.
2. Найдём метки, как это делалось в примере 7. Определим исходную таблицу, являющу-юся инициализацией для расстановки меток:
Таблица 5. Инициализация основной таблицы
и просто выпишем результаты последовательных итераций:
Таблица 5.1. Итерация 1
Таблица 5.2. Итерация 2
Таблица 5.3. Итерация 3
Оказалось невозможным пометить вершину 4 (сток), поскольку обе дуги: (2, 4) и (3, 4) на-сыщены в прямом направлении (в них поток равен ограничению). Нет ни одной вершины в со-стоянии 2. В соответствии с АФФ это означает, что поток u = (6, 4, 0, 6, 4), найденный перед по-следними итерациями, является максимальным потоком, т.е. потоком, величина которого Р (u) максимальна. Так как сумма потоков в дугах, выходящих из источника, равна 10, то величина максимального потока Р (u) = 10 ■
Задание 6. Используя АФФ, найти максимальные потоки в сетях, показанных на рисунке. Для образца см. пример 11.
01 
| 02 
|
03 
| 04 
|
05 
| 06 
|
07 
| 08 
|
09 
| 10 
|
11 
| 12 
|
13 
| 14 
|
15 
| 16
|
■
Задание 7. Используя АФФ, найти максимальный поток в сети с графом, показанным на рис.1, и со следующими пропускными способностями:
1) (12,7,3,1,2,11,14,13,5,6,12,7).
2) (3,4,18,4,5,19,3,4,8,2,7,3).
3) (1,9,4,27,8,33,5,25,3,2,5,20).
4) (9,6,4,28,3,2,31,4,22,5,2,7,).
5) (24,5,8,9,29,3,2,6,33,41,2,21).
6) (9,28,27,10,8,9,6,19,8,3,7,24).
7) (5,8,7,8,5,2,11,2,3,8,18,9).
8) (10,3,2,29,35,41,8,5,27,10,7,9).
9) (44,15,8,3,32,39,8,7,25,29,3,12).
10) (22,5,28,19,4,6,8,1,19,7,4,4).
11) (5,8,1,4,15,33,4,22,5,30,1,2).
12) (11,14,13,5,8,18,9,10,3,27,10,8).
13) (9,6,19,8,3,2,31,33,4,22,5,5).
14) (4,6,8,1,19,7,4,8,7,3,12,22) ■
Предметный указатель
Дуга, (не) насыщенная
в обратном направлении
в прямом направлении
Источник
Поток в сети
Поток по дуге
Поток, максимальный
Поток через разрез
Потока, величина
Пропускная способность вершины
дуги
разреза
Пути, инкремент
прямая дуга
обратная дуга
Путь увеличивающий
Разрез, минимальный
Разреза, обратная дуга
прямая дуга
Расстановки пометок алгоритм
Сети, разрез
Сеть 1-го рода
2-го рода
Сеть, потоковая
Сток
Форда-Фалкерсона алгоритм (АФФ)
Глава 8. Кратчайшие пути
1. Понятие кратчайшего пути
2. Алгоритм Дейкстры
3. Алгоритм Флойда-Уоршолла
4. Минимаксная модификация задачи о кратчайших путях
5. Предметный указатель
Понятие кратчайшего пути
Задачи поиска путей минимальной общей длины, часто называемых кратчайшими путями, являются одними из наиболее исследованных и востребованных задач дискретной оптимиза-ции. Это связано с широкой распространённостью разнообразных прикладных задач, которые сводятся к поиску кратчайших путей. При этом в исходных постановках в качестве длин дуг или рёбер могут выступать расстояния, времена, стоимости, штрафы, убытки – словом, любая величина, которую желательно минимизировать и которая обладает свойством аддитивности или другими «декомпозиционными» свойствами, позволяющими использовать аналогичные модифицированные алгоритмы (примеры таких модификаций рассмотрены в разделе 4). Из множества методов нахождения кратчайших путей в главу включены два метода: алгоритм Дейкстры и алгоритм Флойда-Уоршолла. Различие между ними состоит в том, что первый на каждой итерации находит кратчайший путь от заданной вершины в некоторую другую; поэтому кратчайший путь между двумя фиксированными вершинами зачастую находится гораздо быст-рее, чем кратчайшие пути для всех пар вершин. Второй, напротив, в рамках одной процедуры находит кратчайшие пути сразу для всех пар вершин, что требуется в некоторых приложениях, но при этом вплоть до последней итерации нет гарантии, что кратчайший путь найден для лю-бой заранее указанной парой вершин. Однако алгоритм Флойда-Уоршолла «попутно» решает важную задачу о нахождении цикла отрицательной длины, к которой сводится хорошо известная задача о назначении (подробнее о ней говорится в следующей главе).
Для упрощения обозначений в данной главе рассматриваются простые ориентированные и неориентированные графы. Напомним, что простым называется граф (орграф), любые две вер-шины которого соединены не более чем одним ребром (двумя противоположно направленными дугами). Все понятия и результаты главы легко переносятся с неориентированных графов на ориентированные и наоборот. Переносятся они и на случай графов общего вида (с «параллель-ными» дугами или рёбрами), которые иногда называются мультиграфами (в этой терминологии графами называются только простые графы).
С каждой дугой (ребром) (x, y) заданного графа G ассоциировано число l (x, y), называемое длиной дуги. Содержательно это число может быть расстоянием, стоимостью, пропускной спо-собностью и т.д; Удобно считать, что рассматриваемые графы являются полными, т.е. любые две различные вершины соединены двумя противоположно ориентированными дугами (одним ребром), но для реально отсутствующих дуг l (x, y) = ¥.
С каждым путём P в графе (орграфе) G связано неотрицательное число L (P) (далее назы-ваемое длинойпути P). В этом и следующих двух разделах предполагается, что вес пути равен сумме длин входящих в него дуг. Для любых двух вершин графа G минимальным или кратчайшим путём называется любой соединяющий их путь P с минимальной длиной L (P). Подробнее: путь P, соединяющий заданные вершины a и b, называется минимальным или крат-чайшим, если для любого другого пути P', соединяющего те же самые вершины a и b, верно, что L (P) ≤ L (P'). В случаях, когда веса дуг могут быть отрицательными, задача нахождения кратчайшего пути в такой общей постановке может не иметь решения. В этих случаях обычно рассматриваются не все пути, а только простые пути или цепи (см. раздел 6-3), т.е. пути, про-ходящие через любую вершину или дугу не более одного раза.
Основными задачами, рассматриваемыми и решаемыми в настоящей главе, являются сле-дующие:
1) для заданной вершины найти кратчайшие пути, соединяющие её со всеми осталь-ными вершинами графа G;
2) для всех пар вершинграфа G найти соединяющие их кратчайшие пути.
Конечно, решение первой задачи, применённое ко всем вершинам графа, даёт решение второй задачи, а решение второй задачи даёт решение первой для всех вершин. Различие сос-тоит в алгоритмах, непосредственно направленных на решение либо первой, либо второй зада-чи. Одним из наиболее эффективных методов решения первой задачи является алгоритм Дейкстры (АД), а второй задачи – алгоритм Флойда-Уоршолла (АФУ).
Материал главы организован следующим образом. В разделе 2 вводится в рассмотрение и излагается АД. В разделе 3 вводится в рассмотрение и излагается алгоритм АФУ. Здесь же в от-дельном подразделе устанавливается возможность нахождения циклов отрицательной длины с помощью АФУ. В разделе 4 рассматривается другая зависимость длины пути от входящих в не-го рёбер (дуг). Именно, считается, что длиной пути является длина того ребра (той дуги), кото-рая является максимальной среди длин всех рёбер (дуг), входящих в данный путь.
Как и в других главах, изложение сопровождается иллюстрирующими примерами и зада-ниями.
Алгоритм Дейкстры
Идея алгоритма построения дерева кратчайших путей и определения их весов, предложен-ного в 1959г. Е. Дейкстрой, такова. На каждом этапе одна новая вершина включается в множес-тво S отмеченных вершин, для которых кратчайшие пути из начальной вершины а уже найде-ны. Тогда на следующем этапе к множеству S добавляется вершина b с самым коротким путем из а, все вершины которого, кроме b,содержатся в S.
Предполагается, что неориентированный граф G = á X, Е ñ содержит n вершин. Без ограни-чения общности можно считать, что все вершины задаются номерами от 0 до n –1 и что началь-ная вершина имеет номер 0. Длина ребра (i, j) между вершинами i и j обозначена через l (i, j); если нет ребра, соединяющего эти вершины, то l (i, j) = ¥. Длина пути L (P) равна сумме длин входящих в него рёбер. Для того, чтобы на рисунках не спутывались длины рёбер и номера вершин, вершины на них обозначены как X0, X1, и т.д. вместо 0, 1, и т.д.
Алгоритм Дейкстры (АД). Рассматриваемый алгоритм основан на расстановке пос- тоянных и временных меток у вершин графа G. Метка является вещественным числом или символом ∞.
Как постоянная, так и временная метка у любой вершины х представляет собой длину не-которого пути из начальной вершины в данную вершину х. Если метка является символом ∞, то это значит, что никакой путь из начальной вершины в данную вершину х ещё не определён. На каждой итерации одна из временных меток становится постоянной и далее уже не меняется (она равна длине искомого кратчайшего пути в данную вершину). Постоянные метки обозначе-ны буквой P, временные - буквой T. Через с обозначена последняя (на данный момент) поме-ченная вершина, через R (x) - вершина, предшествующую вершине x на кратчайшем пути из начальной вершины 0 в вершину x.
Шаг 0 (Инициализация). Положить
P (0) = 0, c = 0, T (x) = ¥ (для всех вершин x ≠ 0); R (x) при инициализации не задаётся, поскольку предшествующие вершины ещё не определены).
Шаг i. Выполнить следующие операции:
А. Для каждой вершины x с временной меткой сделать следующее:
1) положить
Z = P (c) + l (c, x); (1)
2) если Z < T (x), положить T (x) = Z, R (x) = c. В противном случае T (x) и R (x) не меняются.
Б. Найти вершину x с минимальной временной меткой (если несколько вершин имеют од-ну и ту же минимальную временную метку, можно выбрать любую из них); положить c = x; по-ложить в качестве постоянной метки P (с) её временную метку T (с).
В. Если ещё остались вершины с временными метками, положить i = i +1 и перейти к шагу i. В противном случае переходим к шагу F.
