Шаг F. На этом шаге определяются кратчайшие пути из начальной вершины 0 во все вершины x ≠0. Кратчайший путь из начальной вершины 0 в любую другую вершину x строится следующим образом: вершиной, предшествующей x на искомом пути, является вершина y = R (x); вершиной, предшествующей y на искомом пути, является вершина z = R (y), и т.д., вплоть до начальной вершины 0. Искомый путь из 0 в x состоит из тех же вершин в обратном порядке ■
При «ручной» реализации АД будет удобно промежуточные результаты записывать в таб-лицу, строки которой соответствуют итерациям, а столбцы (кроме двух левых) – вершинам. В самом левом столбце будем писать номер итерации, а 2-ой слева столбец выделим для записи очередной помечаемой вершины с и её постоянной метки P (с). Каждую клетку в остальных столбцах таблицы разделим на 3 части, в которые будем записывать текущее значение Z, новое значение временной метки Т и новую предыдущую вершину R, или писать старые значения, в зависимости от результата сравнения в пункте 2) шага i -A. После того, как вершина получила постоянную метку, в её клетки ничего не записываем. Числа l (c, x) – длины рёбер – берутся непосредственно из рисунка.
Пример 1. Рассмотрим применение АД для графа, показанного на рис.1. Длины рёбер на-писаны на рисунке прямо около них. Составим вышеупомянутую таблицу.
Рис.1. Граф с длинами рёбер
Таблица 1
| Итера- ция | Последняя помеченная | Вершина 0 | Вершина 1 | Вершина 2 | Вершина 3 | Вершина 4 | Вершина 5 | |||||||||||||
| № | с | P | Z | T | R | Z | T | R | Z | T | R | Z | T | R | Z | T | R | Z | T | R |
| ∞ | ∞ | ∞ | ∞ | ∞ | ||||||||||||||||
| ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | |||||||||||||||
| ∞ | ∞ | |||||||||||||||||||
| ∞ | ∞ | ∞ | ||||||||||||||||||
Дадим пояснения к заполнению таблицы 1. На 0-ой итерации (инициализации) в соответс-твии с АД начальной вершине 0 присваиваем постоянную метку 0 (оба числа заносятся в 0-ую строку в столбце «Последняя помеченная»). Остальные вершины получают временную метку ∞, которая и заносится в 0-ую строку под буквами T. В остальные позиции 0-ой строки в соот-ветствии с АД ничего не заносится.
На 1-ой итерации обрабатываются только столбцы, соответствующие вершинам, имею-щим временные метки. Таковыми в этот момент являются все вершины, кроме вершины 0. Вы-числяем числа Z для всех этих вершин. Так как на 0-ой итерации с = 0, P (c) = 0, то имеем (см. граф) P (0)+ l (0,1)=1, P (0)+ l (0,2)=5, P (0)+ l (0, х)=∞ для х =3,4,5. Поэтому в 1-ую строку под знаком Z записываются числа 1, 5 и знаки ∞, ∞, ∞. Далее, сравнивая эти значения со значениями T из предыдущей строки, записываем под знаком T в данную строку минимумы, а под знаком R в тех столбцах, где произошли изменения в T – последнюю помеченную вершину изстолбца с (в данном случае 0). Выбирая минимальное значение из записанных значений T, получаем 1 в столбце для вершины 1. Поэтому записываем 1 (номер вершины) под с и 1 (длина кратчайшего пути) под P.
На 2-ой итерации обрабатываются только столбцы, соответствующие вершинам 2, 3, 4 и 5. Так как на 1-ой итерации с =1, P (c)=1, то имеем (см. граф) P (1)+ l (1,2)=9, P (1)+ l (1,3)=11, P (1)+ l (1,4)=7, P (1)+ l (1,5)=∞. Поэтому во 2-ую строку под знаком Z записываются числа 9,11,7 и знак ∞. В клетке справа и сверху от этих чисел записаны (под знаком T) предыдущие временные метки: 5,∞,∞,∞. В клетку во 2-ой строке под знаком T записываем новые временные метки - наименьшие значения из этих двух чисел; получаем 5,11,7 и ∞. Под знаком R в 3-ей и 4-ой группах столбцов во 2-ой строке пишется текущий номер c =1. Выбирая минимальное значение из записанных значений T, получаем 5 в столбце для вершины 2. Поэтому записываем 2 (номер вершины) под с и 5 (длина кратчайшего пути) под P.
На 3-ьей итерации обрабатываются только столбцы, соответствующие вершинам 3,4 и 5. Так как на 2-ой итерации с =2, P (c)=5, то имеем (см. граф) P (2)+ l (2,3)=∞, P (2)+ l (2,4)=12, P (2)+ l (2,5) = ∞. Поэтому в 3-ью строку под знаком Z записываются ∞, 12, ∞. В клетке справа и сверху от этих чисел записаны (под знаком T) предыдущие временные метки: 11, 7,∞. В клетку в 3-ьей строке под знаком T записываем новые временные метки - наименьшие значения из этих пар чисел: 11, 7 и ∞. Под знаком R во всех трёх столбцах ничего не меняется, так как временные метки в них не изменились. Выбирая минимальное значение из записанных значений T, получа-ем 7 в столбце для вершины 4. Поэтому записываем 4 (номер вершины) под с и 7 (длина крат-чайшего пути) под P.
На 4-ой итерации рассматриваются только две вершины: 3 и 5. Новые временные метки для них совпадают. В этом случае можно выбрать любую. Выбираем вершину 3 и в соответст-вии с этим заполняем 4-ую строку и далее – последнюю, 5-ую строку.
Найдём теперь, в соответствии с шагом F АД, сами кратчайшие пути. Просматриваем вершины в том порядке, в каком они идут во 2-ом столбце (в этом порядке они получают посто-янные метки).
Для вершины 1 последнее заполненное значение под знаком R равно 0. Это означает, что предпоследней вершиной на кратчайшем пути из 0 в 1 является начальная вершина 0. Поэтому имеем путь 0→1 длины 1.
Для вершины 2 последнее заполненное значение под знаком R равно 0. Это означает, что предпоследней вершиной на кратчайшем пути из 0 в 2 является начальная вершина 0. Поэтому имеем путь 0→2 длины 5.
Для вершины 4 последнее заполненное значение под знаком R равно 1. Это означает, что предпоследней вершиной на кратчайшем пути из 0 в 4 является вершина 1. Поскольку для вер-шины 1 кратчайший путь таков: 0→1, то имеем путь 0→1→4 длины 7.
Для вершины 3 последнее заполненное значение под знаком R равно 1. Это означает, что предпоследней вершиной на кратчайшем пути из 0 в 3 является вершина 1. Поскольку для вер-шины 1 кратчайший путь таков: 0→1, то имеем путь 0→1→3 длины 11.
Для вершины 5 последнее заполненное значение под знаком R равно 4. Это означает, что предпоследней вершиной на кратчайшем пути из 0 в 5 является вершина 4. Поскольку для вер-шины 4 кратчайший путь таков: 0→1→4, то имеем путь 0→1→4→5 длины 11 ■
Пример 2. Рассмотрим применение АД для графа, показанного на рис.1. Длины рёбер на-писаны на рисунке прямо около них. Составим вышеупомянутую таблицу 2. Она содержит все ответы, найденные аналогично примеру 1.
Кратчайшие пути из вершины 0 таковы:
в вершину 1: 0→1;
в вершину 5: 0→5;
в вершину 2: 0→1→2;
в вершину 3: 0→1→3;
в вершину 4: 0→1→4;
в вершину 7: 0→1→2→7;
в вершину 6: 0→5→6.
Длины путей находятся в столбцах «Последний помеченный». Слева стоят номера вершин в порядке получения постоянных меток; справа – длины кратчайших путей в эти вершины.
Рис.2
Таблица 2
| Итера-ции | Посл помеч | Вершина 0 | Вершина 1 | Вершина 2 | Вершина 3 | Вершина 4 | Вершина 5 | Вершина 6 | Вершина 7 | |||||||||||||||||
| № | c | P | Z | T | R | Z | T | R | Z | T | R | Z | T | R | Z | T | R | Z | T | R | Z | T | R | Z | T | R |
| ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ||||||||||||||||||||
| ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | |||||||||||||||||||
| ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ||||||||||||||||||||
| ∞ | ∞ | ∞ | ∞ | ∞ | ||||||||||||||||||||||
| ∞ | ∞ | |||||||||||||||||||||||||
| ∞ | ∞ | |||||||||||||||||||||||||
■
Задание 1. Используя АД, найти кратчайшие пути между вершиной 0 и остальными вершинами в заданных графах. Длины рёбер написаны рядом с рёбрами.
■
Замечание. Рассмотренный алгоритм находит кратчайшие пути в неориентированном графе. Однако этот же самый алгоритм находит кратчайшие ориентированные пути в ориенти-рованном графе (см. все определения в разделе 6-3). Просто в описании алгоритма надо все упоминаемые там рёбра заменить на дуги. В частности, l (c, x) будет означать длину дуги (c, x), ведущей из вершины c в вершину x.
Алгоритм Флойда-Уоршолла
В этом разделе рассматривается другой способ решения задачи о кратчайших путях для всех пар вершин ориентированного графа. В отличие от алгоритма Дейкстры, в АФУ допуска-ются дуги с отрицательной длиной. Однако циклы с отрицательной длиной запрещаются; точн-ее, предполагается, что такие циклы в рассматриваемом графе G = á X, V ñ отсутствуют. Если же циклы отрицательной длины присутствуют, то этот факт выясняется уже в процессе выполнения алгоритма
АФУ основан на представлении пути, ведущего из вершины a в вершину b и проходяще-го через промежуточную вершину c как последовательность двух путей: из a в c и из c в b. По-нятно, что если этот путь является кратчайшим среди всех путей того же вида (т.е. ведущих из a в b через c), то указанные части также должны быть кратчайшими. В алгоритме особую роль играют промежуточные вершины с максимальным номером (в некоторой заданной нумерации вершин). Промежуточной вершиной простого пути р = á v 1, v 2,..., vl ñ будем называть любую из вершин v 2,..., vl −1.
Будем считать, что вершины графа G = á X, V ñ занумерованы числами от 1 до n. Длина дуги с началом в вершине i и концом в вершине j обозначена через l (i, j) (как и в других ситуациях, l (i, j) = 0, если i = j,и l (i, j) = ∞, если дуги(i, j)в графе нет). Рассмотрим произвольное k ≤ n. Для данной пары вершин i, j Î V рассмотрим все пути из i в j, у которых все промежуточные вершины принадлежат множеству {1, 2, …, k }. Пусть p − путь минимальной длины среди всех таких путей. Он является простым путём, поскольку предполагается, что в графе нет циклов отрицательной длины. Как найти длину этого пути, зная длины всех таких (кратчайших) путей для всех пар вершин при мéньших k?
Для пути p есть две возможности.
Если k не входит в р, все промежуточные вершины пути p содержатся в множестве {1, 2, …, k −1}. Тогда путь р является кратчайшим путём из i в j, промежуточные вершины которого принадлежат множеству{1, 2, …, k −1}.
Если k является промежуточной вершиной пути р, она разбивает его на два участка р 1 и р 2 (вершина k встречается лишь однажды, гак как р − простой путь). Поэтому путь р 1 будет кратчайшим путём из i в k,путь р 2будет кратчайшим путём из k в j,а промежуточными вершинами на обоих путях будут вершины из множества {1, 2, …, k −1}. Эти рассуждения лежат в основе излагаемого ниже алгоритма.
Алгоритм Флойда-Уоршолла (АФУ). Алгоритм находит кратчайшие пути для всех пар вершин заданного ориентированного графа G. Для реализации алгоритма вводятся четыре квадратные матрицы размера n ´ n, где n – число вершин в заданном графе G:
Матрица D = (dij) текущих кратчайших расстояний;
Вспомогательная матрица H = (hij) для пересчёта текущих кратчайших расстояний;
Матрица предшествия Π = (πij) (матрица предпоследних вершин на текущих кратчайших путях из i в j);
Вспомогательная матрица Ψ = (ψij) для пересчёта предпоследних вершин.
В процессе работы алгоритма происходит заполнение матриц и изменение их элементов. Алго-ритм прекращает работу после n- го шага.
Шаг 0 (Инициализация). Положить
dij = l (i, j) (i, j = 1, …, n);
πij = 
.
Шаг k (1≤ k ≤ n).
1. Для всех i, j = 1, …, n выполнить следующие операции:
1.1. Положить
z = dik + dkj, (2)
1.2. Если z < dij, то положить hij = z и ψij = πkj. В противном случае положить hij = dij и ψij = πij. Заметим, что из dik = ∞ следует, что z = ∞ и неравенство z < dij не выполняется.
2. Для всех i, j = 1, …, n положить dij = hij, πij = ψij.
Шаг F. На этом шаге определяются кратчайшие пути для всех пар вершин. Кратчайший путь из начальной вершины i в любую другую вершину j строится следующим образом: верши-ной, предшествующей j на искомом пути, является вершина p = πij; вершиной, предшест-вующей p на искомом пути, является вершина q = πip, и т.д., вплоть до начальной вершины i. Искомый путь из i в j состоит из тех же вершин в обратном порядке ■
При «ручной» реализации АФУ будет удобно результаты каждой итерации записывать в последовательные таблицы специального вида – по одной на каждую итерацию. Реализация АФУ состоит в последовательном заполнении таблиц и переносе части результатов в следую-щую таблицу. Эта схема подробно описана при нахождении всех кратчайших путей в конкрет-ном графе, рассмотренном в следующем примере.
Пример 3. Проиллюстрируем работу АФУ на примере графа, показанного на рис.3. На этом рисунке рядом с вершинами показаны их номера; более крупным шрифтом рядом с дуга-ми показаны их длины.
Рис. 3. Ориентированный граф с 5-ью вершинами и 9-ью дугами
Все операции алгоритма являются операциями над данными, записанными в таблицу типа таблицы 3. В эту таблицу входит 5×5 ячеек, каждая из которых состоит из трёх клеток. Эти клетки будут называться левой, средней и правой. Кроме этих 25 ячеек, таблица содержит ле-вый столбец, состоящий из 5-и клеток, и верхнюю строку, состоящую из 5 ячеек, содержащих по 2 клетки каждая (левую и правую). Их роль будет указана ниже.
Таблица 3. Исходная таблица для АФУ
| № | |||||||||||||||||||||
Инициализация. Она состоит в заполнении таблицы 4.1а, совпадающей с таблицей 3. По-следовательно рассматриваются все дуги исходного графа, показанного на рис.3. Если дуга ве-дёт из вершины i в вершину j, то в среднюю клетку ячейки с индексом (i, j) (т.е. находящуюся на пересечении i -ой строки и j -го столбца) вставляется длина дуги из вершины i в вершину j, а в правую клетку – номер i. После этого во всех ячейках с совпадающими индексами (i, i) в среднюю клетку записывается 0. Наконец, во всех остальных ячейках в средние клетки напи-шем знак ∞. Больше ничего в таблицу 4.1а не записывается. Все упомянутые данные берутся непосредственно из рис.3. В дальнейших конструкциях рисунок не участвует.
Таблица 4. Результат инициализации
| № | |||||||||||||||||||||
| ∞ | −4 | ||||||||||||||||||||
| ∞ | ∞ | ||||||||||||||||||||
| ∞ | ∞ | ∞ | |||||||||||||||||||
| ∞ | −5 | ∞ | |||||||||||||||||||
| ∞ | ∞ | ∞ | |||||||||||||||||||
Итерация 1. k = 1. На итерации 1 происходит последовательное преобразование данных, полученных при инициализации и представленных в таблице 4. Сначала заполняются левый столбец и верхняя строка. В i -ую клетку левого столбца копируется содержимое из средней клетки ячейки с индексом (i, k) (номер k равен номеру итерации, и в данном случае k = 1). В j -ую ячейку верхней строки копируется содержимое средней и правой клеток ячейки с индексом (k, j) (k = 1). Результат этой операции приведён в таблице 4.1a. Заметим, что при копировании пустой клетки её копия также будет пустой клеткой.
