Поиск максимального потока. 5 страница

Таблица 4.5. Результат итерации 5

№

−3

−4

−4

−1

−1

−5

−2

 

Шаг F. Найдём сами кратчайшие пути, используя правые клетки в ячейках. Напомним, что число в правой клетке в ячейке (i, j) – это номер вершины, предшествующей на кратчайшем пути из i в j вершине j, т.е. номер предпоследней вершины на этом пути.

Для пути из 1 в 2 такой вершиной является вершина 3 (см. таблицу 4.5); далее, для пути из 1 в 3 такой вершиной является вершина 4; для пути из 1 в 4 такой вершиной является вершина 5; наконец, для пути из 1 в 5 такой вершиной является вершина 1. Таким образом, кратчайший путь из вершины 1 в вершину 2 таков: 1→5→4→3→2. По построению, все промежуточные пу-ти: 1→5→4→3; 1→5→4; 1→5 также являются не только кратчайшими путями, но и именно те-ми кратчайшими путями, которые найдены данным алгоритмом. Все кратчайшие пути из вер-шины 1 уже найдены. Они таковы: 1→5→4→3→2; 1→5→4→3; 1→5→4; 1→5.

Далее, рассмотрим пути из вершины 2 в другие вершины. На пути из 2 в 1 предпоследней вершиной является вершина 4, а непосредственно перед ней – начальная вершина 2, и весь путь таков: 2→4→1. Далее, на пути из 2 в 3 предпоследней вершиной является 4, и путь таков: 2→4 →3. Путь из 2 в 4 состоит из одной дуги 2→4. Наконец, на пути из 2 в 5 предпоследней верши-ной является 1, а путь из 2 в 1 уже известен, поэтому имеем кратчайший путь 2→4→1→5. Все кратчайшие пути из вершины 2 таковы: 2→4→1; 2→4→3; 2→4; 2→4→1→5.

Кратчайшие пути из вершины 3 таковы: 3→5→4→1; 3→2; 3→5→4; 3→5.

Кратчайшие пути из вершины 4 таковы: 4→1; 4→3→2; 4→3; 4→1→5.

Кратчайшие пути из вершины 5 таковы: 5→4→1; 5→4→3→2; 5→4→3; 5→4 ■

3.1. Циклы отрицательной длины. В АФУ предполагалось, что в заданном графе отсутс-твуют циклы отрицательной длины. При обосновании АФУ это требование существенно, так как само разбиение пути, проходящего через вершину k, на два пути, не содержащих k в качест-ве промежуточной вершины, возможно только при единственном вхождении k в путь, что, в свою очередь, гарантируется как раз отсутствием циклов отрицательной длины. Поскольку в достаточно сложных случаях сам факт наличия или отсутствия таких циклов не является оче-видным, необходим специальный алгоритм, устанавливающий этот факт. Более того, в некоторых практически важных задачах (см. главу 9) требуется найти цикл отрицательной длины или установить их отсутствие безотносительно к нахождению кратчайших путей.

Оказывается, что решение этой проблемы является «побочным продуктом» АФУ. Подроб-нее. Применяем АФУ к произвольному графу, не выясняя заранее, содержит ли он циклы отрицательной длины. Для этого после каждого шага, начиная с 1-го (k =1), проверяем все числа на диагонали матрицы D (напомним, что после инициализации все они равны 0). Пусть хотя бы один элемент (скажем, d_ii) оказывается меньше 0. Тогда путь с концом в вершине i, найден-ный так же, как и приведённый сразу после описания АФУ способ нахождения кратчайшего пути в вершину i, окажется циклом с началом и концом в вершине i, длина которого равна от-рицательному числу d_ii. Это следует просто из описания алгоритма, который на каждом k- о м шаге находит текущие кратчайшие пути для всех пар вершин (включая пары с совпадающими

вершинами)

Пример 4. Проиллюстрируем работу АФУ на примере графа, показанного на рис. 4. В нём есть цикл 3→1→2→3 отрицательной длины −1.Всоответствии с описанием «руч-ной» версии АФУ в примере 3, в результате инициализации получим таблицу 5. Далее, на итерации 1 из таблицы 5 получаем преобразо-ванную таблицу 5.1 точно так же, как это дела-лось в примере 3, а затем точно так же полу-чаем таблицы 5.2 и 5.3. После выполнения итерации 3 обнаружи-ваем путь из вершины 1 в ту же самую верши-ну 1, на котором предпоследней вершиной яв-

Рис. 4. Граф с отрицательным циклом

ляется вершина 3, перед ней – вершина 2, а перед вершиной 2 – опять вершина 1. Таким обра-зом, найден цикл 1→2→3→1; длина этого цикла, указанная в средней клетке ячейки (1, 1), рав-на −1, т.е. найден цикл отрицательной длины. Разумеется, одновременно найдены циклы2→3

→1→2 и 3→1→2→3, отличающиеся от цикла 1→2→3→1 только начальной вершиной; их

длина также равна −1.

Таблица 5. Результаты инициализации

№

∞

∞

∞

−3

∞

∞

∞

∞

Таблица 5.1. Результат итерации 1

№

∞

∞

∞

−3

−2

∞

∞

∞

Таблица 5.2. Результат итерации 2

№

∞

−3

−2

−1

−1

∞

∞

∞

Таблица 5.3. Результат итерации 3

№

−1

−2

−1

−4

−3

−2

−2

∞

∞

∞

■

Таким образом, АФУ позволяет не только установить факт наличия или отсутствия цик-лов отрицательной длины, но и найти по крайней мере один из них.

Задание 2. Используя АФУ, в заданном ориентированном графе найтикратчайшие пути между всеми парами вершин, если циклы отрицательной длины не существуют, или найти такой цикл. Для образца см. примеры 3 и 4.

01 02

03 04

 

05 06

 

07 08

 

09 10

 

11 12

13 14

 

15 16

 

17 18

19 20

■

Замечание. Рассмотренный алгоритм находит кратчайшие пути и циклы отрицательной длины в ориентированном графе. Однако этот же самый алгоритм находит соответствующие пути и циклы в неориентированном графе (см. все определения в разделе 6-3). Просто в описа-нии алгоритма надо все упоминаемые там дуги заменить рёбрами. Например, l (c, x) обозначает длину ребра (c, x) с концами c и x.