Главная Промышленная автоматика.

HEAD

Рис. 6.5. Другое представление списков смежности для графа из рис. 6.1

АТД для ориентированных графов

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

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

for каждая вершина w, смежная с вершиной v do

{ некоторые действия с вершиной vi } (6.1)

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

1. FIRST(i) возвращает индекс первой вершины, смежной с вершиной v. Если вершина V не имеет смежных вершин, то возвращается "нулевая" вершина Л.

2. NEXT(o, О возвращает индекс вершины, смежной с вершиной v, следующий за индексом i. Если i - это индекс последней вершины, смежной с вершиной v, то возвращается Л.

3. VERTEX(r. i) возвращает вершину с индексом i из множества вершин, смежных с v.

Пример 6.5. Если для представления орграфа используется матрица смежности, то функция VERTEX(u, i) просто возвращает индекс i. Реализация функций FIRST(i;) и NEXT(u, i) представлена в листинге 6.1. В этом листинге матрица смежности А размера и х и определена вне этих функций с помощью следующего объявления: array [1..П, 1..л] of boolean



в этой матрице О обозначает отсутствие дуги. Эти функции позволяют реализовать оператор (6.1) так, как показано в листинге 6.2. Отметим, что функцию FIRST(u) можно реализовать как NEXT(u, 0). □

Листинг 6.1. Операторы просмотра множества смежных вершин

function first ( v: integer ) : integer;

i: integer;

begin

for i;= 1 to л do

if Hvr i] then return(i);

return(0) { вершина v не имеет смежных вершин) end; { FIRST )

function next ( v: integer; i: integer): integer;

J: integer;

begin

for J:= i + 1 to л do if A[v, j] then return ij);

return(0)

end; { next }

Листинг 6.2. Последовательный просмотр вершин, смежных с вершиной

1: = FIRST (v) ;

while i о О do begin VERTEX (v 1) ; { действия с вершиной w } i:= NEXT{v, i)

6.3. Задача нахождения кратчайшего пути

в этом разделе мы рассмотрим задачи нахождения путей в ориентированном графе. Пусть есть ориентированный граф G = (V, Е), у которого все дуги имеют неотри-! нательные метки (стоимости дуг), а одна верщина определена как источник. Задача состоит в нахождении стоимости кратчайщих путей от источника ко всем другим верщинам графа G (здесь длина пути определяется как сумма стоимостей дуг, составляющих путь). Эта задача часто называется задачей нахождения кратчайшего пути с одним источником. Отметим, что мы будем говорить о длине пути даже тогда, когда она измеряется в других, не линейных, единицах измерения, например во временных единицах.

Можно представить орграф G в виде карты маршрутов рейсовых полетов из одного города в другой, где каждая верщина соответствует городу, а дуга v w - рейсовому маршруту из города v в город w. Метка дуги v -> w - это время полета из горо-

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



да V в город и>. В этом случае рещение задачи нахождения кратчайщего пути с одним источником для ориентированного графа трактуется как минимальное время перелетов между различными городами.

Для рещения поставленной задачи будем использовать "жадный" (см. раздел 1.1) алгоритм, который часто называют алгоритмом Дейкстры (Dijkstra). Алгоритм строит множество S верщин, для которых кратчайшие пути от источника уже известны. На каждом щаге к множеству S добавляется та из оставшихся верщин, расстояние до которой от источника меньще, чем для других оставшихся верщин. Если стоимости всех дуг неотрицательны, то можно быть уверенным, что кратчайший путь от источника к конкретной верщине проходит только через верщины множества S. Назовем такой путь особым. На каждом щаге алгоритма используется также массив D, в который записываются длины кратчайших особых путей для каждой верщины. Когда множество S будет содержать все верщины орграфа, т.е. для всех верщин будут найдены "особые" пути, тогда массив D будет содержать длины кратчайших путей от источника к каждой верщине.

Алгоритм Дейкстры представлен в листинге 6.3. Здесь предполагается, что в орграфе G верщины поименованы целыми числами, т.е. множество верщин V = {1, 2, л}, причем вфшина 1 является источником. Массив С - это двумерный массив стоимостей, где элемент Cfi, j] равен стоимости дуги / ->j. Если дуги i- j не существует, то C[i,jJ ложится равным «>, т.е. большим любой фактической стоимости дуг. На каждом щаге DfiJ содержит длину текущего кратчайщего особого пути к верщине /.

Листинг 6.3. Алгоритм Дейкстры

procedure Dijkstra; begin

(1) S:= {1};

(2) for i:= 2 to n do

(3) /)(!]:= C[l, 1]; { инициализация D } C4) for i:= 1 to n - 1 do begin

(5) выбор из множества V\S такой вершины w,

что значение Dlw] минимально;

(6) добавить W к множеству S;

С7) for каждая вершина v из множества V\S do

(8) D[v] := min(D[v] , D[w] + C[w, v])

end; { Dijkstra )

Пример 6.6. Применим алгоритм Дейкстры для ориентированного графа, показанного на рис. 6.6. Вначале S = (1), Ц 2] = 10, ЩЗ] = <», ЩЦ = 30 и Д5] = 100. На первом щаге цикла (строки (4) - (8) листинга 6.3) w = 2, т.е. верщина 2 имеет минимальное значение в массиве D. Затем вычисляем D[3] = min(oo, 10 + 50) = 60. D[4] и D[5] не изменяются, так как не существует дуг, исходящих из верщины 2 и ведущих к верщинам 4 и 5. Последовательность значений элементов массива D после каждой итерации цикла показаны в табл. 6.1. D

Несложно внести изменения в алгоритм так, чтобы можно было определить сам кратчайший путь (т.е. последовательность верщин) для любой верщины. Для этого надо ввести еще один массив Р верщин, где PfvJ содержит верщину, непосредственно предшествующую верщине v в кратчайшем пути. Вначале положим P[v] = 1 для всех V Ф \. Ъ листинге 6.3 после строки (8) надо записать условный оператор с условием

Можно предположить, что в данном случае в качестве модели больше подходит неориентированный граф, поскольку метки дуг v -> w и и> -> v могут совпадать. Но фактически в большинстве случаях время полета в противоположных направлениях между двумя городами различно. Кроме того, предположение о совпадении меток дуг vwiiw-vHS влияет (и не помогает) на решение задачи нахождения кратчайшего пути.





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 [58] 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123

0.0018