Структуры данных и алгоритмы (1021739), страница 47
Текст из файла (страница 47)
Наиболее общие операторы, выполняемые над ориентированными графами,^включают операторы чтения меток вершин и дуг, вставки и удаления вершин и дуги оператор перемещения по последовательностям дуг.Последний оператор требует небольших пояснений. Часто в программах встречаются операторы, которые неформально можно описать подобно следующему оператору:for каждая вершина w, смежная с вершиной v do{ некоторые действия с вершиной w }(6.1)Для реализации такого оператора необходим индексный тип данных для работы смножеством вершин, смежных с заданной вершиной и.
Например, если для представления орграфа используются списки смежности, то индекс — это позиция в списке смежности вершины и. Если применяется матрица смежности, тогда индекс —целое число, соответствующее смежной вершине. Для просмотра множества смежныхвершин необходимы следующие три оператора.1.FIRST(u) возвращает индекс первой вершины, смежной с вершиной и.
Если вершина v не имеет смежных вершин, то возвращается "нулевая" вершина Л.2. NEXT(u, l) возвращает индекс вершины, смежной с вершиной v, следующий заиндексом i. Если i — это индекс последней вершины, смежной с вершиной v, товозвращается Л.3. VERTEX(i>, i) возвращает вершину с индексом I из множества вершин, смежных с v.Пример 6.5. Если для представления орграфа используется матрица смежности,то функция VERTEX(u, i) просто возвращает индекс i. Реализация функций FIRST(u)и NEXT(y, i) представлена в листинге 6.1.
В этом листинге матрица смежности Аразмера п х п определена вне этих функций с помощью следующего объявления:array [1..л, l . . n ] of boolean186ГЛАВА 6. ОРИЕНТИРОВАННЫЕ ГРАФЫВ этой матрице 0 обозначает отсутствие дуги. Эти функции позволяют реализоватьоператор (6.1) так, как показано в листинге 6.2. Отметим, что функцию FIRST(u)можно реализовать как NEXT(v, 0). ПЛистинг 6.1.
Операторы просмотра множества смежных вершинfunction FIRST ( v: integer ): integer;'vari: integer;beginfor i:= 1 to л doif A[v, i] thenreturn(i);return(0) { вершина v не имеет смежных вершин)end,- { FIRST }function NEXT ( v: integer; i: integer): integer;varj: integer;beginfor j:= i + 1 to n doif A[v, j] thenreturn(j);return(0)end; { NEXT };Листинг 6.2. Последовательный просмотр вершин, смежных с вершиной vi:= FIRST(v) ;while i <> 0 do beginw:= VERTEX(v, i);{ действия с вершиной w }i:= NEXT(v, i)end6.3. Задача нахождения кратчайшего путиВ этом разделе мы рассмотрим задачи нахождения путей в ориентированном графе. Пусть есть ориентированный граф G = (V, Е), у которого все дуги имеют неотри-1цательные метки (стоимости дуг), а одна вершина определена как источник.
Задачасостоит в нахождении стоимости кратчайших путей от источника ко всем другимвершинам графа G (здесь длина пути определяется как сумма стоимостей дуг, составляющих путь). Эта задача часто называется задачей нахождения кратчайшегопути с одним источником1. Отметим, что мы будем говорить о длине пути даже тогда, когда она измеряется в других, не линейных, единицах измерения, например вовременных единицах.Можно представить орграф G в виде карты маршрутов рейсовых полетов из одного города в другой, где каждая вершина соответствует городу, а дуга v —» w — рейсовому маршруту из города и в город w.
Метка дуги v —» w — это время полета из горо1Может показаться, что более естественной задачей будет нахождение кратчайшего пути отисточника к определенной вершине назначения. Но эта задача в общем случае имеет такой жеуровень сложности, что и задача нахождения кратчайшего пути для всех вершин графа (за исключением того "счастливого" случая, когда путь к вершине назначения будет найден ранее,чем просмотрены пути ко всем вершинам графа).6.3. ЗАДАЧА НАХОЖДЕНИЯ КРАТЧАЙШЕГО ПУТИ181да и в город ц)1. В этом случае решение задачи нахождения кратчайшего пути с одним источником для ориентированного графа трактуется как минимальное время перелетов между различными городами.Для решения поставленной задачи будем использовать "жадный" (см.
раздел 1.1)алгоритм, который часто называют алгоритмом Дейкстры (Dijkstra). Алгоритмстроит множество S вершин, для которых кратчайшие пути от источника уже известны. На каждом шаге к множеству S добавляется та из оставшихся вершин, расстояние до которой от источника меньше, чем для других оставшихся вершин. Еслистоимости всех дуг неотрицательны, то можно быть уверенным, что кратчайшийпуть от источника к конкретной вершине проходит только через вершины множестваS. Назовем такой путь особым. На каждом шаге алгоритма используется также массив D, в который записываются длины кратчайших особых путей для каждой вершины. Когда множество S будет содержать все вершины орграфа, т.е.
для всех вершин будут найдены "особые" пути, тогда массив D будет содержать длины кратчайших путей от источника к каждой вершине.Алгоритм Дейкстры представлен в листинге 6.3. Здесь предполагается, что в орграфе G вершины поименованы целыми числами, т.е. множество вершин V— {1, 2, ..., л},причем вершина 1 является источником.
Массив С — это двумерный массив стоимостей, где элемент C[i, j] равен стоимости дуги i -» j. Если дуги I —> j не существует, тоC[i, j] ложится равным °°, т.е. большим любой фактической стоимости дуг. На каждомшаге D[i] содержит длину текущего кратчайшего особого пути к вершине i.Листинг 6.3. Алгоритм Дейкстрыprocedure Dijkstra;begin(1)(2)(3)(4)(5)(6)(7)(8)S:= {!};for i: = 2 to n doD [ i ] : = C[l, i]; { инициализация D }for i:= 1 to n - 1 do beginвыбор из множества V\S такой вершины w,что значение D[w] минимально;добавить w к множеству S;for каждая вершина v из множества V\S doD[v] := min(D[v] , D(w] + C[w, v])endend; { Dijkstra }Пример 6.6.
Применим алгоритм Дейкстры для ориентированного графа, показанного на рис. 6.6. Вначале S = {!}, D[2] = 10, D[3] = °°, D[4] = 30 и D[5] = 100. Напервом шаге цикла (строки (4) - (8) листинга 6.3) w = 2, т.е. вершина 2 имеет минимальное значение в массиве D. Затем вычисляем Z>[3] = min(~, 10 + 50) = 60. Z>[4] иD[5] не изменяются, так как не существует дуг, исходящих из вершины 2 и ведущихк вершинам 4 и 5. Последовательность значений элементов массива D после каждойитерации цикла показаны в табл.
6.1. DНесложно внести изменения в алгоритм так, чтобы можно было определить самкратчайший путь (т.е. последовательность вершин) для любой вершины. Для этогонадо ввести еще один массив Р вершин, где P[v] содержит вершину, непосредственнопредшествующую вершине v в кратчайшем пути. Вначале положим P[v] = 1 для всехv * 1. В листинге 6.3 после строки (8) надо записать условный оператор с условием1Можно предположить, что в данном случае в качестве модели больше подходит неориентированный граф, поскольку метки дуг v -» w и ID -» v могут совпадать. Но фактически вбольшинстве случаях время полета в противоположных направлениях между двумя городамиразлично.
Кроме того, предположение о совпадении меток дуг и —» ы> и w —» р не влияет (и непомогает) на решение задачи нахождения кратчайшего пути.188ГЛАВА 6. ОРИЕНТИРОВАННЫЕ ГРАФЫD[u/J + С[ы), v] < D[v], при выполнении которого элементу Р[и] присваивается значение w. После выполнения алгоритма кратчайший путь к каждой вершине можнонайти с помощью обратного прохождения по предшествующим вершинам массива Р.Рис. 6.6. Орграфченными дугамиспоме-Таблица 6.1.
Вычисления по алгоритму Дейкстры для орграфа из рис. 6.6ИтерацияSwD[2]D[3]C[4]fi[5]Начало{1}-10оо301001{1,2}21060301002<1, 2, 4}4105030903{1, 2, 4, 3}3105030604{1, 2, 4, 3, 5}510503060Пример 6.7. Для орграфа из примера 6.6 массив Р имеет следующие значения:Р[2] = 1, Р[3] = 4, Р[4] = 1, Р[5] = 3. Для определения кратчайшего пути, напримерот вершины 1 к вершине 5, надо отследить в обратном порядке предшествующиевершины, начиная с вершины 5. На основании значений массива Р определяем, чтовершине 5 предшествует вершина 3, вершине 3 — вершина 4, а ей, в свою очередь, — вершина 1.
Таким образом, кратчайший путь из вершины 1 в вершину 5 составляет следующая последовательность вершин: 1, 4, 3, 5. ПОбоснование алгоритма ДейкстрыАлгоритм Дейкстры — пример алгоритма, где "жадность" окупается в том смысле, что если что-то "хорошо" локально, то оно будет "хорошо" и глобально.
В данномслучае что-то локально "хорошее" — это вычисленное расстояние от источника квершине ш, которая пока не входит в множество S, но имеет кратчайший особыйпуть. (Напомним, что особым мы назвали путь, который проходит только через вершины множества S.) Чтобы понять, почему не может быть другого кратчайшего, ноне особого, пути, рассмотрим рис. 6.7. Здесь показан гипотетический кратчайшийпуть к вершине w, который сначала проходит до вершины х через вершины множества S, затем после вершины х путь, возможно, несколько раз входит в множество Sи выходит из него, пока не достигнет вершины ш.Но если этот путь короче кратчайшего особого пути к вершине w, то и начальныйсегмент пути от источника к вершине х (который тоже является особым путем) такжекороче, чем особый путь к w.
Но в таком случае в строке (5) листинга 6.3 при выборевершины w мы должны были выбрать не эту вершину1, а вершину х, поскольку Щ.х]меньше D[u>]. Таким образом, мы пришли к противоречию, следовательно, не может6.3. ЗАДАЧА НАХОЖДЕНИЯ КРАТЧАЙШЕГО ПУТИ189.быть другого кратчайшего пути к вершине w, кроме особого. (Отметим здесь определяющую роль того факта, что все стоимости дуг неотрицательны, без этого свойствапомеченного орграфа алгоритм Дейкстры не будет работать правильно.)Множество SРис. 6.7.
Гипотетический, кратчайший путь к вершине wДля завершения обоснования алгоритма Дейкстры надо еще доказать, что D[v]действительно показывает кратчайшее расстояние до вершины и. Рассмотрим добавление новой вершины w к множеству 5 (строка (6) листинга 6.3), после чего происходит пересчет элементов массива D в строках (7), (8) этого листинга; при этом может получиться более короткий особый путь к некоторой вершине и, проходящийчерез вершину w. Если часть этого пути до вершины w проходит через вершины предыдущего множества S и затем непосредственно к вершине и, то стоимость этого пути, Щш} + С[и>, и], в строке (8) листинга 6.3 сравнивается с Щу] и, если новый путькороче, изменяется значение D[v].Существует еще одна гипотетическая возможность кратчайшего особого пути квершине и, которая показана на рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
